A Scheme for Computing Minimum Covers within Simple Regions

作者：Katz Matthew J^*; Morgenstern Gila

来源：Algorithmica, 2012, 62(1-2): 349-360.

DOI：10.1007/s00453-010-9458-1

• Geometric optimization
• Covering
• Chordal graphs

Let X be a simple region (e.g., a simple polygon), and let Q be a set of points in X. Let O be a convex object, such as a disk, a square, or an equilateral triangle. We present a scheme for computing a minimum cover of Q, consisting of homothets of O contained in X. In particular, a minimum disk cover of Q with respect to X, can be computed in polynomial time.

• 出版日期2012-2