On arrangements of Jordan arcs with three intersections per pair
Edelsbrunner H, Guibas L, Hershberger J, Pach J, Pollack R, Seidel R, Sharir M, Snoeyink J. 1989. On arrangements of Jordan arcs with three intersections per pair. Discrete & Computational Geometry. 4(1), 523–539.
Download (ext.)
Journal Article
| Published
| English
Scopus indexed
Author
Edelsbrunner, HerbertISTA 
;
Guibas, Leonidas;
Hershberger, John;
Pach, János;
Pollack, Richard;
Seidel, Raimund;
Sharir, Micha;
Snoeyink, Jack
;
Guibas, Leonidas;
Hershberger, John;
Pach, János;
Pollack, Richard;
Seidel, Raimund;
Sharir, Micha;
Snoeyink, JackAbstract
Motivated by a number of motion-planning questions, we investigate in this paper some general topological and combinatorial properties of the boundary of the union ofn regions bounded by Jordan curves in the plane. We show that, under some fairly weak conditions, a simply connected surface can be constructed that exactly covers this union and whose boundary has combinatorial complexity that is nearly linear, even though the covered region can have quadratic complexity. In the case where our regions are delimited by Jordan acrs in the upper halfplane starting and ending on thex-axis such that any pair of arcs intersect in at most three points, we prove that the total number of subarcs that appear on the boundary of the union is only (n(n)), where(n) is the extremely slowly growing functional inverse of Ackermann's function.
Publishing Year
Date Published
1989-12-01
Journal Title
Discrete & Computational Geometry
Acknowledgement
The first author is pleased to acknowledge the support of Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and National Science Foundation Grant CCR-8714565. Work on this paper by the fourth and seventh authors has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation and the IBM Corporation. The seventh author in addition wishes to acknowledge support by a research grant from the NCRD—the Israeli National Council for Research and Development. The fifth author would like to acknowledge support in part by NSF grant DMS-8501947. Finally, the eighth author was supported in part by a National Science Foundation Graduate Fellowship.
Volume
4
Issue
1
Page
523 - 539
ISSN
eISSN
IST-REx-ID
Cite this
Edelsbrunner H, Guibas L, Hershberger J, et al. On arrangements of Jordan arcs with three intersections per pair. Discrete & Computational Geometry. 1989;4(1):523-539. doi:10.1007/BF02187745
Edelsbrunner, H., Guibas, L., Hershberger, J., Pach, J., Pollack, R., Seidel, R., … Snoeyink, J. (1989). On arrangements of Jordan arcs with three intersections per pair. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/BF02187745
Edelsbrunner, Herbert, Leonidas Guibas, John Hershberger, János Pach, Richard Pollack, Raimund Seidel, Micha Sharir, and Jack Snoeyink. “On Arrangements of Jordan Arcs with Three Intersections per Pair.” Discrete & Computational Geometry. Springer, 1989. https://doi.org/10.1007/BF02187745.
H. Edelsbrunner et al., “On arrangements of Jordan arcs with three intersections per pair,” Discrete & Computational Geometry, vol. 4, no. 1. Springer, pp. 523–539, 1989.
Edelsbrunner H, Guibas L, Hershberger J, Pach J, Pollack R, Seidel R, Sharir M, Snoeyink J. 1989. On arrangements of Jordan arcs with three intersections per pair. Discrete & Computational Geometry. 4(1), 523–539.
Edelsbrunner, Herbert, et al. “On Arrangements of Jordan Arcs with Three Intersections per Pair.” Discrete & Computational Geometry, vol. 4, no. 1, Springer, 1989, pp. 523–39, doi:10.1007/BF02187745.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Google Scholar