Computing Largest Circles Separating Two Sets of SegmentsReport as inadecuate

Computing Largest Circles Separating Two Sets of Segments - Download this document for free, or read online. Document in PDF available to download.

1 PRISME - Geometry, Algorithms and Robotics CRISAM - Inria Sophia Antipolis - Méditerranée 2 Departement d-Informatique et d-ingénierie Québec 3 University of Ottawa Ottawa

Abstract : 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 Thetan 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 Omegan^2 times, our algorithm can be adapted to work in On alphan log n time and On alphan space, where alphan represents the extremely slowly growing inverse of the Ackermann function.

Author: Jean-Daniel Boissonnat - Jurek Czyzowicz - Olivier Devillers - Jorge Urrutia - Mariette Yvinec -



Related documents