Name
Abstract | ||
|---|---|---|
This paper studies (pointed, or minimal) pseudo- triangulations for a given point set in the plane. Pseudo- triangulations have many properties of triangulations, and have more freedom since polygons with more than three vertices are allowed as long as exactly three have angles less than . In particular, there is a natural flip operation on every internal edge. We establish fundamental properties of pointed pseudo-triangulations. We also present an algorithm to enumerate the pseudo-triangulations of a given point set, based on the greedy flip of Pocchiola and Vegter. Our two independent implementations agree, and allow us to exper- imentally verify or disprove conjectures on the numbers of pseudo-triangulations and triangulations of a given point set. (For example, we establish that #T #PT for all sets of n 10 points.) |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1137/050631008 | Algorithm Engineering and Experimentation |
Keywords | Field | DocType |
pointed pseudotriangulations,greedy flip algorithm,point set,discrete comput,independent implementation,combinatorics,pseudotriangulation,algorithm,triangulation,enumeration | Discrete mathematics,Combinatorics,Enumeration,Algorithm,Pseudotriangle,Greedy algorithm,Triangulation (social science),Point set,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
36 | 3 | 0097-5397 |
Citations | PageRank | References |
17 | 0.88 | 35 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Herve´ Bro¨nnimann | 1 | 17 | 0.88 |
| Lutz Kettner | 2 | 466 | 31.42 |
| Michel Pocchiola | 3 | 359 | 32.59 |
| Jack Snoeyink | 4 | 2842 | 231.68 |