Polygons Needing Many Flipturns |
| |
Authors: | Therese Biedl |
| |
Institution: | (1) School of Computer Science, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada |
| |
Abstract: | A flipturn on a polygon consists of reversing the order of edges inside a pocket
of the polygon, without changing lengths or slopes. Any polygon with n edges must be
convexified after at most (n − 1)! flipturns. A recent paper showed that in fact it will be
convex after at most n(n−3)/2 flipturns.We give here lower bounds.We construct a polygon
such that if pockets are chosen in a bad way, at least (n − 2)2/4 flipturns are needed to
convexify the polygon. In another construction, (n −1)2/8 flipturns are needed, regardless
of the order in which pockets are chosen. All our bounds are adaptive to a pre-specified
number of distinct slopes of the edges. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|