Paper by Erik D. Demaine
- Oswin Aichholzer, Carmen Cortés, Erik D. Demaine, Vida Dujmović, Jeff Erickson, Henk Meijer, Mark Overmars, Belén Palop, Suneeta Ramaswami, and Godfried T. Toussaint, “Flipturning Polygons”, Discrete & Computational Geometry, volume 28, number 2, August 2002, pages 231–253.
A flipturn is an operation that transforms a nonconvex simple polygon
into another simple polygon, by rotating a concavity 180 degrees around the
midpoint of its bounding convex hull edge. Joss and Shannon proved in 1973
that a sequence of flipturns eventually transforms any simple polygon into a
convex polygon. This paper describes several new results about such flipturn
sequences. We show that any orthogonal polygon is convexified after at most
n − 5 arbitrary flipturns, or at most
5 (n − 4)/6 well-chosen flipturns, improving the
previously best upper bound of (n − 1)!/2. We also show
that any simple polygon can be convexified by at most
n2 − 4n + 1 flipturns,
generalizing earlier results of Ahn et al. These bounds depend
critically on how degenerate cases are handled; we carefully explore several
possibilities. We describe how to maintain both a simple polygon and its
convex hull in O(log4 n) time per flipturn, using a data
structure of size O(n). We show that although flipturn sequences for
the same polygon can have very different lengths, the shape and position of the
final convex polygon is the same for all sequences and can be computed in
O(n log n) time. Finally, we demonstrate that finding
the longest convexifying flipturn sequence of a simple polygon is NP-hard.
- This paper is also available from SpringerLink. An older but longer version is also available as arXiv:cs.CG/0008010 of the Computing Research Repository (CoRR).
- The paper is 22 pages.
- The paper is available in PostScript (1788k), gzipped PostScript (276k), and PDF (356k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- JCDCG2000a (Flipturning Polygons)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated March 15, 2019 by