Type of Publication:  Contribution to a conference collection 
Publication status:  Published 
Author:  Beck, Moritz; Storandt, Sabine 
Year of publication:  2018 
Conference:  29th International Workshop, IWOCA 2018, Jul 16, 2018  Jul 19, 2018, Singapore 
Published in:  Combinatorial Algorithms : 29th International Workshop, IWOCA 2018, Singapore, July 1619, 2018, Proceedings / Iliopoulos, Costats et al. (ed.).  Cham : Springer, 2018.  (Lecture Notes in Computer Science ; 10979).  pp. 6577.  ISSN 03029743.  eISSN 16113349.  ISBN 9783319946665 
DOI (citable link):  https://dx.doi.org/10.1007/9783319946672_6 
Summary: 
Motivated by the art gallery problem, the visibility VCdimension was investigated as a measure for the complexity of polygons in previous work. It was shown that simple polygons exhibit a visibility VCdimension of at most 6. Hence there are 7 classes of simple polygons w.r.t. their visibility VCdimension. The polygons in class 0 are exactly the convex polygons. In this paper, we strive for a more profound understanding of polygons in the other classes. First of all, we seek to find minimum polygons for each class, that is, polygons with a minimum number of vertices for each fixed visibility VCdimension d. Furthermore, we show that for d<4 the respective minimum polygons exhibit only few different visibility structures, which can be represented by so called visibility strings. On the practical side, we describe an algorithm that computes the visibility VCdimension of a given polygon efficiently. We use this tool to analyze the distribution of the visibility VCdimension in different kinds of randomly generated polygons.

Subject (DDC):  004 Computer Science 
Bibliography of Konstanz:  Yes 
Files  Size  Format  View 

There are no files associated with this item. 
BECK, Moritz, Sabine STORANDT, 2018. Minimum Polygons for Fixed Visibility VCDimension. 29th International Workshop, IWOCA 2018. Singapore, Jul 16, 2018  Jul 19, 2018. In: ILIOPOULOS, Costats, ed. and others. Combinatorial Algorithms : 29th International Workshop, IWOCA 2018, Singapore, July 1619, 2018, Proceedings. Cham:Springer, pp. 6577. ISSN 03029743. eISSN 16113349. ISBN 9783319946665. Available under: doi: 10.1007/9783319946672_6
@inproceedings{Beck2018Minim43345, title={Minimum Polygons for Fixed Visibility VCDimension}, year={2018}, doi={10.1007/9783319946672_6}, number={10979}, isbn={9783319946665}, issn={03029743}, address={Cham}, publisher={Springer}, series={Lecture Notes in Computer Science}, booktitle={Combinatorial Algorithms : 29th International Workshop, IWOCA 2018, Singapore, July 1619, 2018, Proceedings}, pages={6577}, editor={Iliopoulos, Costats}, author={Beck, Moritz and Storandt, Sabine} }