Decomposing a simple polygon into trapezoids

@inproceedings{li2007decomposingtrapezoids,
author = "Li, F and Klette, R",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "726--733",
title = "Decomposing a simple polygon into trapezoids",
volume = "4673 LNCS",
year = "2007",
abstract = "Chazelle's triangulation [1] forms today the common basis for linear-time Euclidean shortest path (ESP) calculations (where start and end point are given within a simple polygon). This paper provides an alternative method for subdividing a simple polygon into "basic shapes", using trapezoids instead of triangles. The authors consider the presented method as being substantially simpler than the linear-time triangulation method. However, it requires a sorting step (of a subset of vertices of the given simple polygon); all the other subprocesses are linear time. © Springer-Verlag Berlin Heidelberg 2007.",
isbn = "9783540742715",
issn = "0302-9743",
eissn = "1611-3349",
keyword = "Computational geometry",
keyword = "Euclidean shortest path",
keyword = "Rubberband algorithm",
keyword = "Simple polygon",
language = "eng",
}