Visibility-monotonic polygon deflation

Contributions to Discrete Mathematics

Prosenjit Bose ; Vida Dujmovic ; Nima Hoda ; Pat Morin

关键词: Polygons;    reconfiguration;    deflation;   

学科分类：社会科学、人文和艺术（综合）

来源: University of Calgary * Department of Mathematics and Statistics

【 摘 要 】

A deflated polygon is a polygon with no visibility crossings. We answer a question posed by Devadoss et al. (2012) by presenting a polygon that cannot be deformed via continuous visibility-decreasing motion into a deflated polygon. We show that the least n for which there exists such an n-gon is seven. In order to demonstrate non-deflatability, we use a new combinatorial structure for polygons, the directed dual, which encodes the visibility properties of deflated polygons. We also show that any two deflated polygons with the same directed dual can be deformed, one into the other, through a visibility-preserving deformation.

【 授权许可】

Unknown