4SOCS - School of Computer Science [Quebec] (3480 University Street Montreal, McConnell Engineering Bldg, Rm 318, Quebec, Canada H3A 2A7 - Phone: (514) 398-7071 Fax: (514) 398-3883 - Canada)
McGill University (845, rue Sherbrooke O. Montréal (Québec) Canada H3A 0G4 - Canada)
Abstract : 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.
Type de document :
Communication dans un congrès
10th Canadian Conference on Computational Geometry (CCCG'98), 1998, Montreal, Canada. pp.10-12, 1998
https://hal.inria.fr/inria-00442788
Contributeur : Sylvain Lazard
<>
Soumis le : mercredi 23 décembre 2009 - 09:50:02
Dernière modification le : jeudi 11 janvier 2018 - 06:20:14
Document(s) archivé(s) le : vendredi 18 juin 2010 - 00:04:13
