A new upper bound for the VC-dimension of visibility regions (Q390367): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / review text | |||
The paper is focused on the visibility problem related to the art gallery problem. For a given simple polygon and a finite set of points inside this polygon, the authors show that the biggest realizable number -- so-called VC-dimension of visibility regions in simple polygons -- is less or equal to 14. This conclusion disproves the previously known upper bound 23. Assuming a simple polygon containing a set of 15 points each of whose subsets is visually discernible, the authors firstly show that at most 5 points can be situated inside the convex hull of the 15 points set. Secondly, the authors prove that at most 9 points can be located on the convex hull. | |||
Property / review text: The paper is focused on the visibility problem related to the art gallery problem. For a given simple polygon and a finite set of points inside this polygon, the authors show that the biggest realizable number -- so-called VC-dimension of visibility regions in simple polygons -- is less or equal to 14. This conclusion disproves the previously known upper bound 23. Assuming a simple polygon containing a set of 15 points each of whose subsets is visually discernible, the authors firstly show that at most 5 points can be situated inside the convex hull of the 15 points set. Secondly, the authors prove that at most 9 points can be located on the convex hull. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Ivana Linkeová / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 65D18 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6243350 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
computational geometry | |||
Property / zbMATH Keywords: computational geometry / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
visibility | |||
Property / zbMATH Keywords: visibility / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
VC-dimension | |||
Property / zbMATH Keywords: VC-dimension / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
simple polygon | |||
Property / zbMATH Keywords: simple polygon / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
visually discernible | |||
Property / zbMATH Keywords: visually discernible / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
realizable number | |||
Property / zbMATH Keywords: realizable number / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
visibility regions | |||
Property / zbMATH Keywords: visibility regions / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
art gallery problem | |||
Property / zbMATH Keywords: art gallery problem / rank | |||
Normal rank |
Revision as of 14:56, 29 June 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A new upper bound for the VC-dimension of visibility regions |
scientific article |
Statements
A new upper bound for the VC-dimension of visibility regions (English)
0 references
8 January 2014
0 references
The paper is focused on the visibility problem related to the art gallery problem. For a given simple polygon and a finite set of points inside this polygon, the authors show that the biggest realizable number -- so-called VC-dimension of visibility regions in simple polygons -- is less or equal to 14. This conclusion disproves the previously known upper bound 23. Assuming a simple polygon containing a set of 15 points each of whose subsets is visually discernible, the authors firstly show that at most 5 points can be situated inside the convex hull of the 15 points set. Secondly, the authors prove that at most 9 points can be located on the convex hull.
0 references
computational geometry
0 references
visibility
0 references
VC-dimension
0 references
simple polygon
0 references
visually discernible
0 references
realizable number
0 references
visibility regions
0 references
art gallery problem
0 references