Abstract
Let C be a collection of n Jordan regions in the plane in general position, such that each pair of their boundaries intersect in at most s points, where s is a constant. If the boundaries of two sets in C cross exactly twice, then their intersection points are called regular vertices of the arrangement A(C). Let R (C) denote the set of regular vertices on the boundary of the union of C. We present several bounds on ¦R(C)¦, depending on the type of the sets of C. (i) If each set of C is convex, then ¦R(C)¦ = O(n 1.5+ε) for any ε > 0.1 (ii) If no further assumptions are made on the sets of C, then we show that there is a positive integer r that depends only on s such that ¦R(C)¦ = O(n 2−1/r). (iii) If C consists of two collections C 1 and C 2 where C 1 is a collection of m convex pseudo-disks in the plane (closed Jordan regions with the property that the boundaries of any two of them intersect at most twice), and C 2 is a collection of polygons with a total of n sides, then ¦R(C)¦ = O(m 2/3 n 2/3 + m + n), and this bound is tight in the worst case.
Article PDF
Similar content being viewed by others
References
P. K. Agarwal and J. Erickson, Geometric range searching and its relatives, in Advances in Discrete and Computational Geometry (B. Chazelle, J. E. Goodman and R. Pollack, eds.), AMS Press, Providence, RI, 1998, pp. 1–56.
B. Aronov and M. Sharir, The common exterior of convex polygons in the plane, Comput. Geom. Theory Appl. 8 (1997), 139–149.
M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, Computational Geometry: Algorithms and Applications, Springer-Verlag, Berlin, 1997.
B. Chazelle, Cutting hyperplanes for divide-and-conquer, Discrete Comput. Geom. 9 (1993), 145–158.
B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir, Algorithms for trichromatic line segment problems and polyhedral terrains, Algorithmica 11 (1994), 116–132.
K. Clarkson, New applications of random sampling in computational geometry, Discrete Comput. Geom. 2 (1987), 195–222.
H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, Heidelberg, 1987.
A. Efrat and M. Sharir, The complexity of the union of fat objects in the plane, Discrete Comput. Geom. 23 (2000), 171–189.
D. Halperin and M. Sharir, On disjoint concave chains in arrangements of (pseudo)lines, Inform. Process. Lett. 40 (1991), 189–192.
D. Halperin and M. Sharir, Corrigendum: On disjoint concave chains in arrangements of (pseudo) lines, Inform. Process. Lett. 51 (1994), 53–56.
D. Halperin and M. Sharir, Arrangements and their applications in robotics: recent developments, in The Algorithmic Foundations of Robotics, K. Goldberg, D. Halperin, J. C. Latombe and R. Wilson, eds., A. K. Peters, Boston, MA, 1995, pp. 495–511.
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.
J. Matoušek, J. Pach, M. Sharir, S. Sifrony, and E. Welzl, Fat triangles determine linearly many holes, SIAM J. Comput. 23 (1994) 154–169.
E. E. Moise, Geometric Topology in Dimension 2 and 3, Springer-Verlag, New York, 1977.
J. Pach and P. K. Agarwal, Combinatorial Geometry, Wiley, New York, 1995.
J. Pach and M. Sharir, On the boundary of the union of planar convex sets, Discrete Comput. Geom. 21 (1999), 321–328.
M. Sharir and P. K. Agarwal, Davenport Schinzel Sequences and Their Geometric Applications, Cambridge University Press, New York, 1995.
Author information
Authors and Affiliations
Corresponding author
Additional information
The first and the fourth authors have been supported by a grant from the U.S.-Israeli Binational Science Foundation. Boris Aronov has also been supported by a Sloan Research Fellowship and by NSF Grant CCR-99-72568. Micha Sharir has also been supported by NSF Grants CCR-94-24398 and CCR-93-11127, and by a grant from the G.I.F., the German-Israeli Foundation for Scientific Research and Development. Dan Halperin has been supported by an Alon Fellowship, by the U.S.-Israel Binational Science Foundation, and by the Israel Science Foundation founded by the Israel Academy of Sciences and Humanities. Dan Halperin and Micha Sharir have also been supported by ESPRIT IV LTR Project No. 21957 (CGAL), and by the Hermann Minkowski — Minerva Center for Geometry at Tel Aviv University. Part of the work on this paper was carried out when Boris Aronov was visiting Tel Aviv University in March 1997. A preliminary version of the paper has appeared in Proc. 6th Scandinavian Workshop on Algorithm Theory (SWAT ’98), 1998, pp. 322–334.
Rights and permissions
About this article
Cite this article
Aronov, B., Efrat, A., Halperin, D. et al. On the number of regular vertices of the union of jordan regions. Discrete Comput Geom 25, 203–220 (2001). https://doi.org/10.1007/s00454-001-0001-7
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-001-0001-7