Curve-sensitive cuttings

ABSTRACT

We introduce (1/r)-cuttings for collections of surfaces in 3-space that are sensitive to an additional collection of curves. Specifically, let S be a set of n surfaces in R ³ of constant description complexity, and let C be a set of m curves in R ³ of constant description complexity. Let 1= r = min{ m,n } be a given parameter. We show the existence of a (1/ r )-cutting ? of S of size O ( r ^3+e ), for any e > 0 , such that the number of crossings between the curves of C and the cells of ? is O ( m ^1+e ). The latter bound improves, by roughly a factor of r , the bound that can be obtained for cuttings based on vertical decompositions.We view curve-sensitive cuttings as a powerful tool that is potentially useful in various scenarios that involve curves and surfaces in three dimensions. As a preliminary application, we use the construction to obtain a bound of O ( m ^1/2+e n ^2+e ), for any e > 0 , on the complexity of the multiple zone of m curves in the arrangement of n surfaces in 3-space

REFERENCES

• 1: P. K. Agarwal and M. Sharir, Arrangements and their applications, In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 49--119, Elsevier Science Publishers B.V., North-Holland, Amsterdam, 2000.
• 2: Boris Aronov , Marco Pellegrini , Micha Sharir, On the zone of a surface in a hyperplane arrangement, Discrete & Computational Geometry, v.9 n.2, p.177-186, 1993 [doi>10.1007/BF02189317]
• 3: M. de Berg, L. J. Guibas, and D. Halperin, Vertical decompositions for triangles in 3 -space, Discrete Comput. Geom., 15:35--61, 1996.
• 4: M. de Berg and O. Schwarzkopf, Cuttings and applications, Internat. J. Comput. Geom. Appls., 5:343--355, 1995.
• 5: Bernard Chazelle, Cutting hyperplanes for divide-and-conquer, Discrete & Computational Geometry, v.9 n.2, p.145-158, 1993 [doi>10.1007/BF02189314]
• 6: B. Chazelle and J. Friedman, A deterministic view of random sampling and its use in geometry, Combinatorica, 10:229--249, 1990.
• 7: Bernard Chazelle , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir, A singly exponential stratification scheme for real semi-algebraic varieties and its applications, Theoretical Computer Science, v.84 n.1, p.77-105, July 22, 1991 [doi>10.1016/0304-3975(91)90261-Y]
• 8: Kenneth L. Clarkson , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir , Emo Welzl, Combinatorial complexity bounds for arrangements of curves and spheres, Discrete & Computational Geometry, v.5 n.2, p.99-160, 1990 [doi>10.1007/BF02187783]
• 9: K. Clarkson, New applications of random sampling in computational geometry, Discrete Comput. Geom. 2:195--222, 1987.
• 10: 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]
• 11: David P. Dobkin , David G. Kirkpatrick, Fast Detection of Polyhedral Intersections, Proceedings of the 9th Colloquium on Automata, Languages and Programming, p.154-165, July 12-16, 1982
• 12: Effective Computational Geometry for Curves and Surfaces, Shared-cost RTD (FET Open) Project No IST-2000-26473, http://www-sop.inria.fr/prisme/ECG.
• 13: D. Halperin and M. Sharir, Almost tight upper bounds for the single cell and zone problems in three dimensions, Discrete Comput. Geom. 14:385--410, 1995.
• 14: D. Haussler and E. Welzl, Epsilon-nets and simplex range queries, Discrete Comput. Geom., 2:127--151, 1987.
• 15: 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
• 16: Jiří Matoušek, Construction of &egr;-nets, Discrete & Computational Geometry, v.5 n.5, p.427-448, 1990 [doi>10.1007/BF02187804]
• 17: J. Matouaek. Range searching with efficient hierarchical cuttings, Discrete Comput. Geom., 10:157--182, 1993.
• 18: Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996

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:
arrangements, curves and surfaces, cuttings, many cells, zone