Computing hereditary convex structures

ABSTRACT

Color red and blue the n vertices of a convex polytope P in R³. Can we compute the convex hull of each color class in o(n log n)? What if we have k > 2 colors? What if the colors are random? Consider an arbitrary query halfspace and call the vertices of P inside it blue: can the convex hull of the blue points be computed in time linear in their number? More generally, can we quickly compute the blue hull without looking at the whole polytope? This paper considers several instances of hereditary computation and provides new results for them. In particular, we resolve an eight-year old open problem by showing how to split a convex polytope in linear expected time.

REFERENCES

• 1: A. Aggarwal , L. J. Guibas , J. Saxe , P. W. Shor, A linear-time algorithm for computing the Voronoi diagram of a convex polygon, Discrete & Computational Geometry, v.4 n.6, p.591-604, Sep. 1989 [doi>10.1007/BF02187749]
• 2: Nancy M. Amato , Michael T. Goodrich , Edgar A. Ramos, Linear-time triangulation of a simple polygon made easier via randomization, Proceedings of the sixteenth annual symposium on Computational geometry, p.201-212, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336206]
• 3: Jean-Daniel Boissonnat , Mariette Yvinec, Algorithmic geometry, Cambridge University Press, New York, NY, 1998
• 4: Timothy M. Chan, Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions, SIAM Journal on Computing, v.30 n.2, p.561-575, 2000 [doi>10.1137/S0097539798349188]
• 5: Timothy M. Chan, Three problems about simple polygons, Computational Geometry: Theory and Applications, v.35 n.3, p.209-217, October 2006 [doi>10.1016/j.comgeo.2005.11.002]
• 6: Bernard Chazelle, Filtering search: a new approach to query answering, SIAM Journal on Computing, v.15 n.3, p.703-724, August 1986 [doi>10.1137/0215051]
• 7: Bernard Chazelle, Triangulating a simple polygon in linear time, Discrete & Computational Geometry, v.6 n.5, p.485-524, 1991 [doi>10.1007/BF02574703]
• 8: Bernard Chazelle, An optimal algorithm for intersecting three-dimensional convex polyhedra, SIAM Journal on Computing, v.21 n.4, p.671-696, Aug. 1992 [doi>10.1137/0221041]
• 9: Bernard Chazelle, The discrepancy method: randomness and complexity, Cambridge University Press, New York, NY, 2000
• 10: B. Chazelle, O. Devillers, F. Hurtado, M. Mora, V. Sacristán, and M. Teillaud. Splitting a Delaunay triangulation in linear time. Algorithmica, 34(1):39--46, 2002.
• 11: L. P Chew, Building Voronoi Diagrams for Convex Polygons in Linear Expected Time, Dartmouth College, Hanover, NH, 1990
• 12: L. P. Chew and S. Fortune. Sorting helps for Voronoi diagrams. Algorithmica, 18(2):217--228, 1997.
• 13: F. Chin, J. Snoeyink, and C. A. Wang. Finding the medial axis of a simple polygon in linear time. Discrete Comput. Geom., 21(3):405--420, 1999.
• 14: Francis Chin , Cao An Wang, Finding the Constrained Delaunay Triangulation and Constrained Voronoi Diagram of a Simple Polygon in Linear Time, SIAM Journal on Computing, v.28 n.2, p.471-486, April 1999 [doi>10.1137/S0097539795285916]
• 15: Kenneth L. Clarkson, A randomized algorithm for closest-point queries, SIAM Journal on Computing, v.17 n.4, p.830-847, August 1988 [doi>10.1137/0217052]
• 16: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
• 17: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 18: O. Devillers. Randomization yields simple O(n log sp ast n) algorithms for difficult Ω(n) problems. Internat. J. Comput. Geom. Appl., 2(1):97--111, 1992.
• 19: H. N. Djidjev and A. Lingas. On computing Voronoi diagrams for sorted point sets. Internat. J. Comput. Geom. Appl., 5(3):327--337, 1995.
• 20: Hervé Fournier , Antoine Vigneron, A Tight Lower Bound for Computing the Diameter of a 3D Convex Polytope, Algorithmica, v.49 n.3, p.245-257, October 2007 [doi>10.1007/s00453-007-9010-0]
• 21: R. Klein and A. Lingas. A linear-time randomized algorithm for the bounded Voronoi diagram of a simple polygon. Int. J. Comput. Geometry Appl., 6(3):263--278, 1996.
• 22: Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 23: K. Mulmuley. Computational Geometry: An Introduction through Randomized Algorithms. Prentice-Hall, Englewood Cliffs, 1994.
• 24: Edgar A. Ramos, On range reporting, ray shooting and k-level construction, Proceedings of the fifteenth annual symposium on Computational geometry, p.390-399, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304993]
• 25: Raimund Seidel, A Method for Proving Lower Bounds for Certain Geometric Problems, Cornell University, Ithaca, NY, 1984
• 26: Raimund Seidel, A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons, Computational Geometry: Theory and Applications, v.1 n.1, p.51-64, July 1991 [doi>10.1016/S0925-7721(99)00042-5]
• 27: Marc Kreveld , Maarten Löffler , Joseph S. Mitchell, Preprocessing Imprecise Points and Splitting Triangulations, Proceedings of the 19th International Symposium on Algorithms and Computation, December 15-17, 2008, Gold Coast, Australia [doi>10.1007/978-3-540-92182-0_49]

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

General Terms:
Algorithms, Theory

Keywords:
convex polytope, half-space range searching, hereditary convex hulls