A constant-factor approximation algorithm for vertex guarding a WV-polygon
The problem of vertex guarding a simple polygon was first studied by Subir K. Ghosh (1987), who presented a polynomial-time $O(\log n)$-approximation algorithm for placing as few guards as possible at vertices of a simple $n$-gon $P$, such that every point in $P$ is visible to at least one of the g...
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Artigo |
| Sprache: | Inglês |
| Veröffentlicht: |
Carleton University
2021-12-01
|
| Schriftenreihe: | Journal of Computational Geometry |
| Online-Zugang: | https://jocg.org/index.php/jocg/article/view/3434 |
| Tags: |
Keine Tags, Fügen Sie das erste Tag hinzu!
|