Convexifying Monotone Polygons
| Autor: | Steven M. Robbins, Erik D. Demaine, Michael Soss, Sylvain Lazard, Therese C. Biedl |
|---|---|
| Přispěvatelé: | Department of Computer Science [Calgary] (CPSC), University of Calgary, Models, algorithms and geometry for computer graphics and vision (ISA), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), School of computer science [Ottawa] (SCS), Carleton University, Kamakoti V (IMSC, India) Rangarajan K (MCC, India) Rama R (IIT, Madras, India) Boopal E (IIT, Madras, India), Alok Aggarwal and C. Pandu Rangan |
| Jazyk: | angličtina |
| Rok vydání: | 1999 |
| Předmět: |
Polygon covering
010102 general mathematics [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH] 0102 computer and information sciences Rectilinear polygon Computer Science::Computational Geometry Convex polygon 01 natural sciences Polygon triangulation Combinatorics mécanismes articulés Monotone polygon linkages 010201 computation theory & mathematics Star-shaped polygon TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Polygon Equilateral polygon 0101 mathematics Mathematics MathematicsofComputing_DISCRETEMATHEMATICS ComputingMethodologies_COMPUTERGRAPHICS |
| Zdroj: | Algorithms and Computation ISBN: 9783540669166 ISAAC |
| DOI: | 10.1007/3-540-46632-0_42⟩ |
| Popis: | The original publication is available at www.springerlink.com; International audience; This paper considers reconfigurations of polygons, where each polygon edge is a rigid link, no two of which can cross during the motion. We prove that one can reconfigure any monotone polygon into a convex polygon; a polygon is monotone if any vertical line intersects the interior at a (possibly empty) interval. Our algorithm computes in O(n2) time a sequence of O(n2) moves, each of which rotates just four joints at once. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|