A new upper bound for the VC-dimension of visibility regions (Q390367): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 4 users not shown) | |||
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 | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.comgeo.2013.08.012 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2217505494 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4945520 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Visibility Algorithms in the Plane / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: New Results on Visibility in Simple Polygons / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A new upper bound for the VC-dimension of visibility regions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Guarding galleries where every point sees a large area / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Improved approximation for guarding simple galleries from the perimeter / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Almost tight bounds for \(\epsilon\)-nets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4530626 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3799261 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4945523 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Guarding galleries where no point sees a small area. / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 05:25, 7 July 2024
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