Inapproximability of finding maximum hidden sets on polygons and terrains

DOI10.1016/S0925-7721(01)00029-3zbMath0998.68190WikidataQ126550466 ScholiaQ126550466MaRDI QIDQ5959557

Stephan J. Eidenbenz

Publication date: 14 March 2002

Published in: Computational Geometry (Search for Journal in Brave)

zbMATH Keywords

maximum clique problem

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

FO model checking on geometric graphs, Unnamed Item, Computing the maximum clique in the visibility graph of a simple polygon, Finding minimum hidden guard sets in polygons --- tight approximability results, Unnamed Item

Cites Work

• Guarding polyhedral terrains
• Hiding people in polygons
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Computing the shortest watchtower of a polyhedral terrain in \(O(n\log n)\) time.
• Efficient computation of geodesic shortest paths
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item