A scheme for computing minimum covers within simple regions

DOI10.1007/S00453-010-9458-1MaRDI QIDQ2428655zbMATH OpenOpenAlexFDO

Authors 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

chordal graphscoveringgeometric optimization

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15)

Recommendations

• A Scheme for Computing Minimum Covers within Simple Regions
• Optimal cover of points by disks in a simple polygon
• Optimal cover of points by disks in a simple polygon
• Polynomial time approximation schemes for minimum disk cover problems
• Covering points with minimum/maximum area orthogonally convex polygons

Cites work

• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Almost optimal set covers in finite VC-dimension
• An O ( n log n ) Algorithm for Rectilinear Minimal Spanning Trees
• Approximation schemes for covering and packing problems in image processing and VLSI
• Covering Points by Unit Disks of Fixed Location
• Covering orthogonal polygons with star polygons: The perfect graph approach
• Finding the medial axis of a simple polygon in linear time
• Guarding orthogonal art galleries with sliding cameras
• Minimum-cost coverage of point sets by disks
• On guarding the vertices of rectilinear domains
• POLYGON DECOMPOSITION AND THE ORTHOGONAL ART GALLERY PROBLEM
• PTAS for geometric hitting set problems via local search
• Perfect Graphs and Orthogonally Convex Covers
• Some constrained minimax and maximin location problems
• The 2-center problem with obstacles
• Two-Dimensional Voronoi Diagrams in the L _p -Metric
• Voronoui Diagrams in $L_1 (L_\infty )$ Metrics with 2-Dimensional Storage Applications

Cited in

(3)

• Optimal cover of points by disks in a simple polygon
• A Scheme for Computing Minimum Covers within Simple Regions
• Optimal cover of points by disks in a simple polygon

This page was built for publication: A scheme for computing minimum covers within simple regions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2428655)