Minimum Polygons for Fixed Visibility VC-Dimension

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

BECK, Moritz, Sabine STORANDT, 2018. Minimum Polygons for Fixed Visibility VC-Dimension. 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 16-19, 2018, Proceedings. Cham:Springer, pp. 65-77. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-319-94666-5. Available under: doi: 10.1007/978-3-319-94667-2_6

@inproceedings{Beck2018Minim-43345, title={Minimum Polygons for Fixed Visibility VC-Dimension}, year={2018}, doi={10.1007/978-3-319-94667-2_6}, number={10979}, isbn={978-3-319-94666-5}, issn={0302-9743}, address={Cham}, publisher={Springer}, series={Lecture Notes in Computer Science}, booktitle={Combinatorial Algorithms : 29th International Workshop, IWOCA 2018, Singapore, July 16-19, 2018, Proceedings}, pages={65--77}, editor={Iliopoulos, Costats}, author={Beck, Moritz and Storandt, Sabine} }

2018 Motivated by the art gallery problem, the visibility VC-dimension was investigated as a measure for the complexity of polygons in previous work. It was shown that simple polygons exhibit a visibility VC-dimension of at most 6. Hence there are 7 classes of simple polygons w.r.t. their visibility VC-dimension. 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 VC-dimension 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 VC-dimension of a given polygon efficiently. We use this tool to analyze the distribution of the visibility VC-dimension in different kinds of randomly generated polygons. Beck, Moritz Beck, Moritz eng 2018-09-20T13:33:27Z Storandt, Sabine 2018-09-20T13:33:27Z Minimum Polygons for Fixed Visibility VC-Dimension Storandt, Sabine

This item appears in the following Collection(s)

Search KOPS


My Account