2026-07-22T04:46:22Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:19980 2024-06-06T06:21:14Z ddc:004 open_access
Enclosing Points with Geometric Objects Chan, Timothy M. He, Qizheng Xue, Jie obstacle placement geometric optimization approximation algorithms Let X be a set of points in ℝ² and π’ͺ be a set of geometric objects in ℝ², where |X| + |π’ͺ| = n. We study the problem of computing a minimum subset π’ͺ^* βŠ† π’ͺ that encloses all points in X. Here a point x ∈ X is enclosed by π’ͺ^* if it lies in a bounded connected component of β„Β²βˆ–(⋃_{O ∈ π’ͺ^*} O). We propose two algorithmic frameworks to design polynomial-time approximation algorithms for the problem. The first framework is based on sparsification and min-cut, which results in O(1)-approximation algorithms for unit disks, unit squares, etc. The second framework is based on LP rounding, which results in an O(Ξ±(n)log n)-approximation algorithm for segments, where Ξ±(n) is the inverse Ackermann function, and an O(log n)-approximation algorithm for disks. Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Timothy M. Chan and Qizheng He and Jie Xue 2024 Is Part Of LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2024.35 urn:nbn:de:0030-drops-199802 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.35 eng https://creativecommons.org/licenses/by/4.0/legalcode