Minimizing the Size of Vertexlights in Simple Polygons

&
Mathematical Logic Quarterly 48 (3):447-458 (2002)
  Copy   BIBTEX

Abstract

We show that given a simple Polygon P it is NP-hard to determine the smallest α ∈ [0, π] such that P can be illuminated by α-vertexlights, if we place exactly one α-vertexlight in each vertex of P

Categories

Keywords

Reprint years

DOI

10.1002/1521-3870(200204)48:3

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,010

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons.Dietmar Schuchardt & Hans-Dietrich Hecker - 1995 - Mathematical Logic Quarterly 41 (2):261-267.
A P‐Completeness Result for Visibility Graphs of Simple Polygons.Jana Dietel & Hans-Dietrich Hecker - 2000 - Mathematical Logic Quarterly 46 (3):361-375.
Variants of Visibility and their Complexity.Dietmar Schuchardt & Hans-Dietrich Hecker - 1998 - Mathematical Logic Quarterly 44 (4):522-528.
Quadrilaterizing an Orthogonal Polygon in Parallel.Jana Dietel & Hans-Dietrich Hecker - 1998 - Mathematical Logic Quarterly 44 (1):50-68.
On the ranked points of a Π1 0 set.Douglas Cenzer & Rick L. Smith - 1989 - Journal of Symbolic Logic 54 (3):975-991.
Recursive events in random sequences.George Davie - 2001 - Archive for Mathematical Logic 40 (8):629-638.
P ≠ NP for all infinite Boolean algebras.Mihai Prunescu - 2003 - Mathematical Logic Quarterly 49 (2):210-213.
Iterated local reflection versus iterated consistency.Lev Beklemishev - 1995 - Annals of Pure and Applied Logic 75 (1-2):25-48.
P^f NP^f for almost all f.J. D. Hamkins - 2003 - Mathematical Logic Quarterly 49 (5):536.
P f≠ NP f for almost all f.Joel David Hamkins & Philip D. Welch - 2003 - Mathematical Logic Quarterly 49 (5):536-540.

Analytics

Added to PP
2013-12-01

Downloads
14 (#1,277,709)

6 months
2 (#1,685,650)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references