Complexity of a Single Face in an Arrangement of s-Intersecting Curves

Details Complexity of a Single Face in an Arrangement of s-Intersecting Curves Complexity of a Single Face in an Arrangement of s-Intersecting Curves

2011-08-22

arxiv.org/abs/1108.4336v1

Computer Science

Computational Geometry

9 pages, 5 figures

Scientific paper

Consider a face F in an arrangement of n Jordan curves in the plane, no two of which intersect more than s times. We prove that the combinatorial complexity of F is O(\lambda_s(n)), O(\lambda_{s+1}(n)), and O(\lambda_{s+2}(n)), when the curves are bi-infinite, semi-infinite, or bounded, respectively; \lambda_k(n) is the maximum length of a Davenport-Schinzel sequence of order k on an alphabet of n symbols. Our bounds asymptotically match the known worst-case lower bounds. Our proof settles the still apparently open case of semi-infinite curves. Moreover, it treats the three cases in a fairly uniform fashion.

Affiliated with

Also associated with

No associations

Rating

Complexity of a Single Face in an Arrangement of s-Intersecting Curves does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Complexity of a Single Face in an Arrangement of s-Intersecting Curves, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity of a Single Face in an Arrangement of s-Intersecting Curves will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-176453