Tentative prune-and-search for computing Voronoi vertices

ABSTRACT

This paper gives optimal logarithmic-time algorithms for two problems related to computing vertices of Voronoi diagrams in the plane: 1) given a convex polygon, compute the largest homothet of a given triangle that can be inscribed in the polygon and 2) given three disjoint convex polygons, compute the points that are equidistant from all three. These algorithms are based on a prune-and-search technique that may make tentative discards that are later revoked or certified. In three dimensions, a general strategy using hierarchical data structures leads to poly-logarithmic algorithms for related problems.

REFERENCES

• 1: B. Bhattacharya, P. Egyed, and G. Toussaint. Computing the wingspan of a butterfly. In Proc. Third Can. Conf. Comp. Geom., pages 88-91, Simon Fraser University, Vancouver, 1991.
• 2: B. Chazelle. An optimal algorithm for intersecting three-dimensional convex polyhedra. Technical report, Princeton University, 1989.
• 3: D. P. Dobkin and D. G. Kirkpatrick. Fast detection of polyhedral intersection. Theoretical Comp. Sci., 27:241-253, 1983.
• 4: David P. Dobkin , David G. Kirkpatrick, Determining the separation of preprocessed polyhedra: a unified approach, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.400-413, July 1990, Warwick University, England
• 5: H. Edelsbrunner, Computing the extreme distances between two convex polygons, Journal of Algorithms, v.6 n.2, p.213-224, June 1985 [doi>10.1016/0196-6774(85)90039-2]
• 6: H. Edelsbrunner and H. Maurer. Finding extreme points in three dimensions and solving the postoffice problem in the plane. Info. Proc. Let., pages 39-47, 1985.
• 7: David Eppstein, Dynamic three-dimensional linear programming, Proceedings of the 32nd annual symposium on Foundations of computer science, p.488-494, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185410]
• 8: L. Guibas, j. Hershberger, and J. Snoeyink. Compact interval trees: A data structure for convex hulls. Int. J. Comp. Geom. App., 1(1):1-22, 1991.
• 9: T. C. Kao and D. M. Mount. An algorithm for computing compacted Voronoi diagrams defined by convex distance functions, in Proc. Third Can. Conf. Comp. Geom., pages 104-109, 1991.
• 10: D. Kirkpatrick. Optimal search in planar subdivisions. SIAM J. Comp., 12:28-35, 1983.
• 11: D. Leven and M. $haxir. Planning a purely translational motion for a convex polygonal object in two dimensional space using generalized Voronoi diagrams. Disc. ~4 Comp. Geom., 2:9-31, 1987.
• 12: Andrew K. Martin, A Simple Primal Algorithm for Intersecting 3-Polyhedra in Linear Time, University of British Columbia, Vancouver, BC, Canada, 1991
• 13: M. McAllister, D. Kirkpatrick, and J. Snoeyink. An approximate Voronoi diagram for planning translation motion. In preparation, 1993.
• 14: D. M. Mount. The densest double-lattice packing of a convex polygon. In J. E. Goodman, R. Pollack, and W. Steiger, editors, Discrete and Computational Geometry, pages 245-262. AMS, Providence, RI, 1991.
• 15: M. Overmars and J. van Leeuwen. Maintenance of configurations in the plane. J. Comp. Sys. Sci., 23:166-204, 1981.
• 16: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 17: C. K. Yap. An O(nlogn) algorithm for the Voronoi diagram of a set of simple curve segments. Disc. Comp. Geom., 2:365-393, 1987.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Theory, Verification