Name
Abstract | ||
|---|---|---|
Abstract. Let P and Q be two disjoint convex polygons in the plane with m and n vertices, respectively. Given a point x in P , the aperture angle of x with respect to Q is defined as the angle of the cone that: (1) contains Q , (2) has apex at x and (3) has its two rays emanating from x tangent to Q . We present algorithms with complexities O(n log m) , O(n + n log (m/n)) and O(n + m) for computing the maximum aperture angle with respect to Q when x is allowed to vary in P . To compute the minimum aperture angle we modify the latter algorithm obtaining an O(n + m) algorithm. Finally, we establish an Ω(n + n log (m/n)) time lower bound for the maximization problem and an Ω(m + n) bound for the minimization problem thereby proving the optimality of our algorithms.
|
Year | DOI | Venue |
|---|---|---|
2002 | 10.1007/s00453-001-0112-9 | Algorithmica |
Keywords | Field | DocType |
Key words. Aperture angle,Convexity,Unimodality,Discrete optimization,Algorithms,Complexity,Computational geometry,Robotics,Visibility. | Aperture,Discrete mathematics,Polygon,Combinatorics,Disjoint sets,Vertex (geometry),Upper and lower bounds,Convex polygon,Regular polygon,Tangent,Mathematics | Journal |
Volume | Issue | ISSN |
33 | 4 | 1432-0541 |
Citations | PageRank | References |
4 | 0.53 | 7 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Prosenjit K. Bose | 1 | 2336 | 293.75 |
| Hurtado-Diaz | 2 | 4 | 0.53 |
| Elsa Omaña-Pulido | 3 | 12 | 2.58 |
| Jack Snoeyink | 4 | 2842 | 231.68 |
| Godfried Toussaint | 5 | 1656 | 309.75 |