s'authentifier
version française rss feed

inria-00090667, version 1

Circular Separability of Polygons

Jean-Daniel Boissonnat () 1, Jurek Czyzowicz a2, Olivier Devillers () b1, Mariette Yvinec () 1

Algorithmica 30, 1 (2001) 67--82

Résumé : 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.

  • Domaine : Informatique/Géométrie algorithmique
  • Commentaire : http://www.springerlink.com/content/8q2b1bpn222a30hw/
 
  • inria-00090667, version 1
  • oai:hal.inria.fr:inria-00090667
  • Contributeur : 
  • Soumis le : Vendredi 1 Septembre 2006, 16:05:47
  • Dernière modification le : Vendredi 1 Septembre 2006, 16:07:03
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...