A scheme for computing minimum covers within simple regions

DOI10.1007/s00453-010-9458-1zbMath1286.68467MaRDI QIDQ2428655

Matthew J. Katz, Gila Morgenstern

Publication date: 26 April 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-010-9458-1

zbMATH Keywords

covering; chordal graphs; geometric optimization

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

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

52C15: Packing and covering in (2) dimensions (aspects of discrete geometry)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Covering orthogonal polygons with star polygons: The perfect graph approach
• Finding the medial axis of a simple polygon in linear time
• Almost optimal set covers in finite VC-dimension
• On guarding the vertices of rectilinear domains
• The 2-Center Problem with Obstacles
• GUARDING ORTHOGONAL ART GALLERIES WITH SLIDING CAMERAS
• POLYGON DECOMPOSITION AND THE ORTHOGONAL ART GALLERY PROBLEM
• Approximation schemes for covering and packing problems in image processing and VLSI
• Perfect Graphs and Orthogonally Convex Covers
• Two-Dimensional Voronoi Diagrams in the L _p -Metric
• Voronoui Diagrams in $L_1 (L_\infty )$ Metrics with 2-Dimensional Storage Applications
• An O ( n log n ) Algorithm for Rectilinear Minimal Spanning Trees
• PTAS for geometric hitting set problems via local search
• Covering Points by Unit Disks of Fixed Location
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph