Abstract
We extend the notion ofk-sets and (≤k)-sets (see [3], [12], and [19]) to arrangements of curves and surfaces. In the case of curves in the plane, we assume that each curve is simple and separates the plane. Ak-point is an intersection point of a pair of the curves which is covered by exactlyk interiors of (or half-planes bounded by) other curves; thek-set is the set of allk-points in such an arrangement, and the (≤k)-set is the union of allj-sets, forj≤k. Adapting the probabilistic analysis technique of Clarkson and Shor [13], we obtain bounds that relate the maximum size of the (≤k)-set to the maximum size of a 0-set of a sample of the curves. Using known bounds on the size of such 0-sets we obtain asympotically tight bounds for the maximum size of the (≤k)-set in the following special cases: (i) If each pair of curves intersect at most twice, the maximum size is Θ(nkα(nk)). (ii) If the curves are unbounded arcs and each pair of them intersect at most three times, then the maximum size is Θ(nkα(n/k)). (iii) If the curves arex-monotone arcs and each pair of them intersect in at most some fixed numbers of points, then the maximum size of the (≤k)-set is Θ(k 2λ s (nk)), where λ s (m) is the maximum length of (m,s)-Davenport-Schinzel sequences. We also obtain generalizations of these results to certain classes of surfaces in three and higher dimensions. Finally, we present various applications of these results to arrangements of segments and curves, high-order Voronoi diagrams, partial stabbing of disjoint convex sets in the plane, and more. An interesting application yields andO(n logn) bound on the expected number of vertically visible features in an arrangement ofn horizontal discs when they are stacked on top of each other in random order. This in turn leads to an efficient randomized preprocessing ofn discs in the plane so as to allow fast stabbing queries, in which we want to report all discs containing a query point.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
P. K. Agarwal, Ray shooting and other applications of spanning trees with low stabbing number,Proc. 5th Symp. on Computational Geometry, 1989, pp. 315–325.
P. Agarwal, M. Sharir, and P. Shor, Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences,J. Combin. Theory Ser. A 52 (1989), 228–274.
N. Alon and E. Györi, The number of small semispaces of a finite set of points in the plane,J. Combin. Theory Ser. A 41 (1986), 154–157.
H. Alt, R. Fleischer, M. Kaufmann, K. Mehlhorn, S. Näher, S. Schirra, and C. Uhrig, Approximate motion planning and the complexity of the boundary of the union of simple geometric figures,Proc. 6th Symp. on Computational Geometry, 1990, pp. 281–289.
M. Atallah, Some dynamic computational geometry problems,Comp. Math. Appl. 11 (1985), 1171–1181.
F. Aurenhammer, Power diagrams: Properties, algorithms, and applicationsSIAM J. Comput. 16 (1987), 78–96.
B. Chazelle, Lower bounds on the complexity of polytope range searching,Trans. Amer. Math. Soc. 2 (1989), 637–666.
B. Chazelle and L. Guibas, Fractional cascading: II. Applications,Algorithmica 1 (1986), 163–191.
B. Chazelle, L. Guibas, and D. T. Lee, The power of geometric duality,BIT 25 (1985), 76–90.
B. Chazelle and D. T. Lee, On a circle placement problem,Computing 36 (1986), 1–16.
B. Chazelle and F. P. Preparata, Halfspace range search: An algorithmic application ofk-sets,Discrete Comput. Geom. 1 (1986), 83–93.
K. Clarkson, Applications of random sampling in computational geometry, II,Proc. 4th Symp. on Computational Geometry, 1988, pp. 1–11.
K. Clarkson and P. Short Applications of random sampling in computational geometry, II,Discrete Comput. Geom. 4 (1989), 387–421.
H. Edelsbrunner,Algorithms in Combinatorial Geometry, Springer-Verlag, Heidelberg, 1987.
H. Edelsbrunner, L. Guibas, J. Hershberger, J. Pach, R. Pollack, R. Seidel, M. Sharir, and J. Snoeyink, On arrangements of Jordan arcs with three intersections per pair,Discrete Comput. Geom. 4 (1989), 523–539.
H. Edelsbrunner, L. Guibas, J. Pach, R. Pollack, R. Seidel, and M. Sharir, Arrangements of curves in the plane: Topology, combinatorics and algorithms,Proc 15th Int. Colloq. on Automata, Programming and Languages, 1988, pp. 219–229.
H. Edelsbrunner, L. Guibas, and M. Sharir, The upper envelope of piecewise linear functions: Algorithms and applications,Discrete Comput. Geom. 4 (1989), 311–336.
H. Edelsbrunner and M. Sharir, The maximum number of ways to stabn convex nonintersecting objects in the plane is 2n−2,Discrete Comput. Geom. 5 (1990), 35–42.
J. Goodman and R. Pollack, On the number ofk-subsets of a set ofn points in the plane,J. Combin. Theory Ser. A 36 (1984), 101–104.
S. Hart and M. Sharir, Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes,Combinatorica 6 (1986), 151–177.
M. Katchalski, T. Lewis, and J. Zaks, Geometric permutations for convex sets,Discrete Math. 54 (1985), 271–284.
K. Kedem, R. Livne, J. Pach, and M. Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles,Discrete Comput. Geom. 1 (1986), 59–71.
D. Leven and M. Sharir, Planning a purely translational motion for a convex object in two-dimensional space using generalized Voronoi diagrams,Discrete Comput. Geom. 2 (1987), 9–31.
J. Pach and M. Sharir, The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis,Discrete Comput. Geom. 4 (1989), 291–309.
J. Pach, W. Steiger, and E. Szemerédi, An upper bound on the number of planark-sets,Proc. 30th IEEE Symp. on Foundations of Computer Science, 1989 pp. 72–79.
F. P. Preparata and M. I. Shamos,Computational Geometry: An Introduction, Springer-Verlag, Heidelberg, 1985.
N. Sarnak and R. Tarjan, Planar point location using persistent search trees,Comm. ACM 29 (1986), 669–679.
J. Schwartz and M. Sharir, On the 2-dimensional Davenport-Schinzel problem,J. Symbolic Comput. 10 (1990), 371–393.
R. Wenger, Upper bounds on geometric permutations for convex sets,Discrete Comput. Geom. 5 (1990), 27–33.
A. Wiernik and M. Sharir, Planar realization of nonlinear Davenport-Schinzel sequences by segments,Discrete Comput. Geom. 3 (1988), 15–47.
Author information
Authors and Affiliations
Additional information
Work on this paper has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grants DCR-83-20085 and CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, the NCRD—the Israeli National Council for Research and Development-and the Fund for Basic Research in Electronics, Computers and Communication, administered by the Israeli Academy of Sciences.
Rights and permissions
About this article
Cite this article
Sharir, M. Onk-sets in arrangements of curves and surfaces. Discrete Comput Geom 6, 593–613 (1991). https://doi.org/10.1007/BF02574706
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02574706