Name
Abstract | ||
|---|---|---|
An edge of a simple closed polygon is called eliminating if it can be translated in parallel towards the interior of the polygon to eliminate itself or one of its neighbor edges
without violating simplicity.
In this paper we prove that in each simple closed polygon there exist at least two eliminating edges; this lower bound is tight since for all n ≥ 5 there exists a polygon with only two eliminating edges. Furthermore we present an algorithm that computes in total O(n log n) time using O(n) space an eliminating edge for each elimination step. We thus obtain the first non-trivial algorithm that computes for P a sequence of n − 3 edge translations reducing P to a triangle.
|
Year | DOI | Venue |
|---|---|---|
1998 | 10.1007/BFb0055047 | ICALP |
Keywords | Field | DocType |
simple polygons,improved conjecture,lower bound | Discrete mathematics,Rectilinear polygon,Combinatorics,Polygon,Polygon covering,Computer science,Simple polygon,Star-shaped polygon,Affine-regular polygon,Equiangular polygon,Polygon triangulation | Conference |
Volume | ISSN | ISBN |
1443 | 0302-9743 | 3-540-64781-3 |
Citations | PageRank | References |
2 | 0.46 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Thorsten Graf | 1 | 470 | 21.89 |
| Kamakoti Veezhinathan | 2 | 35 | 4.04 |