Details

Autor(en) / Beteiligte

• Fragoudakis, Christodoulos
• Markou, Euripides
• Zachos, Stathis

Titel

Maximizing the guarded boundary of an Art Gallery is APX-complete

Ist Teil von

• Computational geometry : theory and applications, 2007-10, Vol.38 (3), p.170-180

Ort / Verlag

Elsevier B.V

Erscheinungsjahr

2007

Link zum Volltext

Quelle

ScienceDirect Journals (5 years ago - present)

Beschreibungen/Notizen

• In the Art Gallery problem, given is a polygonal gallery and the goal is to guard the gallery's interior or walls with a number of guards that must be placed strategically in the interior, on walls or on corners of the gallery. Here we consider a more realistic version: exhibits now have size and may have different costs. Moreover the meaning of guarding is relaxed: we use a new concept, that of watching an expensive art item, i.e. overseeing a part of the item. The main result of the paper is that the problem of maximizing the total value of a guarded weighted boundary is APX-complete. This is shown by an appropriate ‘gap-preserving’ reduction from the Max-5-occurrence-3-Sat problem. We also show that this technique can be applied to a number of maximization variations of the art gallery problem. In particular we consider the following problems: given a polygon with or without holes and k available guards, maximize a) the length of walls guarded and b) the total cost of paintings watched or overseen. We prove that all the above problems are APX-complete.