Paper Info
Title
On arrangements of Jordan arcs with three intersections per pair
Abstract
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 of n regions bounded by Jordan curves in the plane. We show that, under some fairly weak conditions, a simply connected Riemann 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 arcs in the upper halfplane starting and ending on the x-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 &THgr;(n&agr;(n)), where &agr;(n) is the extremely slowly growing functional inverse of Ackermann's function.
Year
DOI
Venue
1988
10.1007/BF02187745
Discrete & Computational Geometry - Selected papers from the fourth ACM symposium on computational geometry, Univ. of Illinois, Urbana-Champaign, June 6 8, 1988
Keywords
DocType
Volume
Jordan Curve,Simple Connectivity,Boundary Patch,Jordan Region,Functional Inverse
Conference
4
Issue
ISSN
Citations 
5
0179-5376
10
PageRank 
References 
Authors
2.31
6
8
Name
Order
Citations
PageRank
Herbert Edelsbrunner167871112.29
Leonidas J. Guibas2130841262.73
John Hershberger3102.31
János Pach42366292.28
Richard Pollack5912203.75
raimund seidel6102.31
Micha Sharir784051183.84
Jack Snoeyink82842231.68