Published in

Springer (part of Springer Nature), Algorithmica, 1(30), p. 67-82

DOI: 10.1007/s004530010078

Links

Tools

Export citation

Search in Google Scholar

Circular Separability of Polygons

Journal article published in 2001 by Jean-Daniel Boissonnat, Jurek Czyzowicz, Olivier Devillers ORCID, Mariette Yvinec
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Upload
Green circle
Postprint: archiving allowed
Upload
Red circle
Published version: archiving forbidden
Policy details
Data provided by SHERPA/RoMEO

Abstract

Two planar sets are circularly separable if there exists a circle enclosing one of the set 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.