Computing Largest Circles Separating Two Sets of SegmentsReportar como inadecuado




Computing Largest Circles Separating Two Sets of Segments - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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.





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

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados