Premium
Minimizing the Size of Vertexlights in Simple Polygons
Author(s) -
Spillner Andreas,
Hecker HansDietrich
Publication year - 2002
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/1521-3870(200204)48:3<447::aid-malq447>3.0.co;2-l
Subject(s) - simple (philosophy) , mathematics , combinatorics , polygon (computer graphics) , vertex (graph theory) , simple polygon , regular polygon , geometry , computer science , graph , telecommunications , philosophy , epistemology , frame (networking)
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 .