An Overview of Minimum Convex Cover and Maximum Hidden Set
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908999137361920 |
|---|---|
| author | Browne, Reilly |
| author_facet | Browne, Reilly |
| contents | We give a review of results on the minimum convex cover and maximum hidden set problems. In addition, we give some new results. First we show that it is NP-hard to determine whether a polygon has the same convex cover number as its hidden set number. We then give some important examples in which these quantities don't always coincide. Finally, We present some consequences of insights from Browne, Kasthurirangan, Mitchell and Polishchuk [FOCS, 2023] on other classes of simple polygons. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_01354 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An Overview of Minimum Convex Cover and Maximum Hidden Set Browne, Reilly Computational Geometry We give a review of results on the minimum convex cover and maximum hidden set problems. In addition, we give some new results. First we show that it is NP-hard to determine whether a polygon has the same convex cover number as its hidden set number. We then give some important examples in which these quantities don't always coincide. Finally, We present some consequences of insights from Browne, Kasthurirangan, Mitchell and Polishchuk [FOCS, 2023] on other classes of simple polygons. |
| title | An Overview of Minimum Convex Cover and Maximum Hidden Set |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2403.01354 |