Computing largest circles separating two sets of segments

Details Computing largest circles separating two sets of segments Computing largest circles separating two sets of segments

1999-09-03

arxiv.org/abs/cs/9909005v1

Computer Science

Computational Geometry

14 pages, 3 figures, abstract presented at 8th Canadian Conference on Computational Geometry, 1996

Scientific paper

A circle $C$ separates two planar sets if it encloses one of the sets and its open interior disk does not meet the other set. A separating circle is a largest one if it cannot be locally increased while still separating the two given sets. An Theta(n log n) optimal algorithm is proposed to find all largest circles separating two given sets of line segments when line segments are allowed to meet only at their endpoints. In the general case, when line segments may intersect $\Omega(n^2)$ times, our algorithm can be adapted to work in O(n alpha(n) log n) time and O(n \alpha(n)) space, where alpha(n) represents the extremely slowly growing inverse of the Ackermann function.

Affiliated with

Also associated with

No associations

Rating

Computing largest circles separating two sets of segments 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 Computing largest circles separating two sets of segments, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing largest circles separating two sets of segments will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-543102