Circular Separability of Polygons |
| |
Authors: | J -D Boissonnat J Czyzowicz O Devillers M Yvinec |
| |
Affiliation: | (1) INRIA, 2004 Route des Lucioles, B.P. 109, 06561 Valbonne cedex, France. \{Jean-Daniel.Boissonnat, Olivier. Devillers, Marriette.Yvinec\}@sophia.inria.fr., FR;(2) Département d'informatique, Université du Québec à Hull, Hull, Québec, Canada. czyzowicz@uqah.uquebec.ca., CA |
| |
Abstract: | Two planar sets are circularly separable if there exists a circle enclosing one of the sets and whose open interior disk
does not intersect the other set. This paper studies two problems related to circular separability. A linear-time algorithm
is proposed to decide if two polygons are circularly separable. The algorithm outputs the smallest separating circle. The
second problem asks for the largest circle included in a preprocessed, convex polygon, under some point and/ or line constraints. The resulting circle must contain the query points and it must lie in the halfplanes delimited by the
query lines.
Received October 25, 1998; revised April 21, 1999. |
| |
Keywords: | , Computational geometry, |
本文献已被 SpringerLink 等数据库收录! |
|