The interface between computational and combinatorial geometry

ABSTRACT

We illustrate the rich interface between computational and combinatorial geometry by a series of examples, including k-sets, randomized incremental algorithms, random sampling and partitioning, and analysis of geometric arrangements.

REFERENCES

• 1: Pankaj K. Agarwal , Micha Sharir, Efficient algorithms for geometric optimization, ACM Computing Surveys (CSUR), v.30 n.4, p.412-458, Dec. 1998 [doi>10.1145/299917.299918]
• 2: P. Agarwal and M. Sharir, Davenport-Schinzel sequences and their geometric applications, in Handbook of Computational Geometry, J. R. Sack and J. Urrutia (Eds.), North-Holland, 2000, 1--47.
• 3: P. Agarwal and M. Sharir, Arrangements of surfaces in higher dimensions, in Handbook of Computational Geometry, J. R. Sack and J. Urrutia (Eds.), North-Holland, 2000, 49--119.
• 4: P. K. Agarwal , M. Sharir , P. Shor, Sharp upper and lower bounds on the length of general Davenport-Schinzel Sequences, Journal of Combinatorial Theory Series A, v.52 n.2, p.228-274, Nov. 1989 [doi>10.1016/0097-3165(89)90032-0]
• 5: Pankaj K. Agarwal , Mark de Berg , Jirí Matousek , Otfried Schwarzkopf, Constructing Levels in Arrangements and Higher Order Voronoi Diagrams, SIAM Journal on Computing, v.27 n.3, p.654-667, June 1998 [doi>10.1137/S0097539795281840]
• 6: N Alon , E Györi, The number of small semispaces of a finite set of points in the plane, Journal of Combinatorial Theory Series A, v.41 n.1, p.154-157, Jan. 1986 [doi>10.1016/0097-3165(86)90122-6]
• 7: F. Aurenhammer and R. Klein, Voronoi diagrams, in Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, Eds., Elsevier North Holland, 2000, pp. 201--290.
• 8: S. Basu, On the combinatorial and topological complexity of a single cell, Discrete Comput. Geom. 29 (2003), 41--59.
• 9: J. D. Boissonnat, M. Sharir, B. Tagansky and M. Yvinec, Voronoi diagrams in higher dimensions under certain polyhedral distance functions, Discrete Comput. Geom. 19 (1998), 485--519.
• 10: T. M. Chan, On levels in arrangements of curves, Discrete Comput. Geom. 29 (2003), 375--393.
• 11: Bernard Chazelle , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir, A Singly-Expenential Stratification Scheme for Real Semi-Algebraic Varieties and Its Applications, Proceedings of the 16th International Colloquium on Automata, Languages and Programming, p.179-193, July 11-15, 1989
• 12: B. Chazelle and J. Friedman., A deterministic view of random sampling and its use in geometry, Combinatorica 10 (1990), 229--249.
• 13: L. Paul Chew , Klara Kedem , Micha Sharir , Boaz Tagansky , Emo Welzl, Voronoi diagrams of lines in 3-space under polyhedral convex distance functions, Journal of Algorithms, v.29 n.2, p.238-255, Nov. 1998 [doi>10.1006/jagm.1998.0957]
• 14: K. L. Clarkson, New applications of random sampling in computational geometry, Discrete Comput. Geom. 2 (1987), 195--222.
• 15: 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]
• 16: Richard Cole , Micha Sharir , Chee K Yap, On k-hulls and related problems, SIAM Journal on Computing, v.16 n.1, p.61-77, Feb. 1987 [doi>10.1137/0216005]
• 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: T. K. Dey, Improved bounds for planar k-sets and related problems, Discrete Comput. Geom. 19 (1998), 373--382.
• 19: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 20: Herbert Edelsbrunner , Raimund Seidel, Voronoi diagrams and arrangements, Discrete & Computational Geometry, v.1 n.1, p.25-44, 1986 [doi>10.1007/BF02187681]
• 21: A. Efrat and M. Sharir, The complexity of the union of fat objects in the plane, Discrete Comput. Geom.. 23 (2000), 171--189.
• 22: P. Erdös, L. Lovász, A. Simmons, and E. G. Straus, Dissection graphs of planar point sets, in: A Survey of Combinatorial Theory (J. N. Srivastava et al., eds.), North-Holland, Amsterdam, 1973, 139--149.
• 23: J. E. Goodman and R. Pollack. On the number of k-subsets of a set of n points in the plane. J. Combin. Theory, Ser. A36 (1984), 101--104.
• 24: L. Guibas, D. E. Knuth and M. Sharir, Randomized incremental construction of Voronoi and Delaunay diagrams, Algorithmica 7 (1992), 381--413.
• 25: D. Halperin and M. Sharir, New bounds for lower envelopes in three dimensions with applications to visibility of terrains, Discrete Comput. Geom. 12 (1994), 313--326.
• 26: D. Halperin and M. Sharir, Almost tight upper bounds for the single cell and zone problems in three dimensions, Discrete Comput. Geom. 14 (1995), 385--410.
• 27: S Hart , M Sharir, Nonlinearity of Daveport:80Schinzel sequences and of generalized path compression schemes, Combinatorica, v.6 n.2, p.151-177, 1986 [doi>10.1007/BF02579170]
• 28: D. Haussler and E. Welzl, ∈-nets and simplex range queries, Discrete Comput. Geom. 2 (1987), 127--151.
• 29: D. Huttenlocher, K. Kedem and M. Sharir, The upper envelope of Voronoi surfaces and its applications, Discrete Comput. Geom. 9 (1993), 267--291.
• 30: L. Kavraki, P. Šestka, J.-C. Latombe and M. Overmars, Probabilistic roadmaps for fast path planning in high dimensional configuration spaces, IEEE Trans. Robotics Autom. 12 (1996), 566--580.
• 31: Klara Kedem , Ron Livne , János Pach , Micha Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles, Discrete & Computational Geometry, v.1 n.1, p.59-71, 1986 [doi>10.1007/BF02187683]
• 32: V. Koltun (Machtey Award Co-winner), Almost Tight Upper Bounds for Vertical Decompositions in Four Dimensions, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.56, October 14-17, 2001
• 33: Vladlen Koltun , Micha Sharir, 3-Dimensional Euclidean Voronoi Diagrams of Lines with a Fixed Number of Orientations, SIAM Journal on Computing, v.32 n.3, p.616-642, 2003 [doi>10.1137/S0097539702408387]
• 34: V. Koltun and M. Sharir, Polyhedral Voronoi diagrams of polyhedra in three dimensions, Discrete Comput. Geom. 31 (2004), 83--124.
• 35: L. Lovász, On the number of halving lines, Ann. Univ. Sci. Budapest, Eötvös, Sec. Math. 14 (1971), 107--108.
• 36: J. Matoušek, Derandomization in computational geometry, in Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, Eds., Elsevier North Holland, 2000, pp. 559--595.
• 37: Jiří Matoušek, Efficient partition trees, Discrete & Computational Geometry, v.8 n.3, p.315-334, 1992 [doi>10.1007/BF02293051]
• 38: Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 39: Jiri Matousek , Janos Pach , Micha Sharir , Shmuel Sifrony , Emo Welzl, Fat Triangles Determine Linearly Many Holes, SIAM Journal on Computing, v.23 n.1, p.154-169, Feb. 1994 [doi>10.1137/S009753979018330X]
• 40: J. Milnor, On the Betti numbers of real varieties, Proc. Amer. Math. Soc. 15 (1964), 275--280.
• 41: J. Pach and P. K. Agarwal, Combinatorial Geometry, Wiley, New York, 1995.
• 42: J. Pach, I. Safruti and M. Sharir, The union of congruent cubes in three dimensions, Discrete Comput. Geom. 30 (2003), 133--160.
• 43: J. Pach and M. Sharir, Geometric incidences, in Towards a Theory of Geometric Graphs (J. Pach, ed.), Contemporary Mathematics, Vol. 342, Amer. Math. Soc., Providence, RI, 2004, pp. 185--223.
• 44: Marco Pellegrini, Ray shooting and lines in space, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 45: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 46: J. T. Schwartz and M. Sharir, On the Piano Movers' problem: II. General techniques for computing topological properties of real algebraic manifolds, Advances in Appl. Math. 4 (1983), 298--351.
• 47: 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]
• 48: R. Seidel, Backward analysis of randomized geometric algorithms, in New Trends in Discrete and Computational Geometry, J. Pach, Ed., Algorithms and Combinatorics, Vol. 10, Springer Verlag, 1993, pp. 37--68.
• 49: M. Sharir, Almost tight upper bounds for lower envelopes in higher dimensions, Discrete Comput. Geom. 12 (1994), 327--345.
• 50: M. Sharir, Motion planning, in Handbook of Discrete and Computational Geometry, 2nd Edition (J. E. Goodman and J. O'Rourke, Eds.), CRC Press, Boca Raton, Fla., 2004, 1037--1064.
• 51: M. Sharir, Arrangements of surfaces in higher dimensions, in Advances in Discrete and Computational Geometry (Proc. 1996 AMS Mt. Holyoke Summer Research Conference, B. Chazelle, J. E. Goodman and R. Pollack, Eds.) Contemporary Mathematics No. 223, American Mathematical Society, 1999, 335--353.
• 52: Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
• 53: E. Szemerédi and W. T. Trotter, Extremal problems in discrete geometry, Combinatorica 3 (1983), 381--392.
• 54: R. Thom, Sur l'homologie des varietes algebriques reelles, in: Differential and Combinatorial Topology (S.S. Cairns, ed.), Princeton Univ. Press, 1965, 255--265.
• 55: G. Tóth, Point sets with many k-sets, Discrete Comput. Geom. 26 (2001), 187--194.
• 56: Rephael Wenger, Helly-type theorems and geometric transversals, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997