3532 articles – 5253 Notices  [english version]

inria-00442788, version 1

Convexifying Star-Shaped Polygons

Hazel Everett () 1, Sylvain Lazard () 1, Steve Robbins a, 2, H. Schröder 3, Sue Whitesides 4

10th Canadian Conference on Computational Geometry (CCCG'98) (1998) 10-12

Résumé : We show that all star-shaped simple polygons can be transformed, in O(n) steps each of which takes O(n) time to compute in an extended real RAM model, into convex polygons by continuous motions during which the edges remain rigid and the polygon remains star-shaped and simple. For each step, the trajectories of the vertices are given explicitly. In particular, the vertices move along straight lines, circular-arcs, or on the curve traced by an intersection point of two circles whose centers move along straight lines.

  • a –  MCGILL UNIVERSITY
  • 1 :  VEGAS (INRIA Lorraine - LORIA)
  • INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
  • 2 :  School of computer science [Ottawa] (SCS)
  • Carleton University
  • 3 :  Loughborough University
  • Loughborough University
  • 4 :  School of Computer Science [Quebec] (SOCS)
  • McGill University
  • Domaine : Informatique/Géométrie algorithmique
 
  • inria-00442788, version 1
  • http://hal.inria.fr/inria-00442788
  • oai:hal.inria.fr:inria-00442788
  • Contributeur : Sylvain Lazard <>
  • Soumis le : Mercredi 23 Décembre 2009, 09:50:02
  • Dernière modification le : Mercredi 23 Décembre 2009, 18:24:34