Abstract
Suppose we are given a pair of points s, t and a set ? of n geometric objects in the plane, called obstacles. We show that in polynomial time one can construct an auxiliary (multi)graph G with vertex set ? and every edge labeled from {0, 1}, such that a set ?_d ⊆ ? of obstacles separates s from t if and only if G[?_d] contains a cycle whose sum of labels is odd. Using this structural characterization of separating sets of obstacles we obtain the following algorithmic results.
In the Obstacleremoval problem the task is to find a curve in the plane connecting s to t intersecting at most q obstacles. We give a 2.3146^q n^{O(1)} algorithm for Obstacleremoval, significantly improving upon the previously best known q^{O(q³)} n^{O(1)} algorithm of Eiben and Lokshtanov (SoCG'20). We also obtain an alternative proof of a constant factor approximation algorithm for Obstacleremoval, substantially simplifying the arguments of Kumar et al. (SODA'21).
In the Generalized Pointsseparation problem input consists of the set ? of obstacles, a point set A of k points and p pairs (s₁, t₁), … (s_p, t_p) of points from A. The task is to find a minimum subset ?_r ⊆ ? such that for every i, every curve from s_i to t_i intersects at least one obstacle in ?_r. We obtain 2^{O(p)} n^{O(k)}time algorithm for Generalized Pointsseparation. This resolves an open problem of Cabello and Giannopoulos (SoCG'13), who asked about the existence of such an algorithm for the special case where (s₁, t₁), … (s_p, t_p) contains all the pairs of points in A. Finally, we improve the running time of our algorithm to f(p,k) ⋅ n^{O(√k)} when the obstacles are unit disks, where f(p,k) = 2^{O(p)} k^{O(k)}, and show that, assuming the Exponential Time Hypothesis (ETH), the running time dependence on k of our algorithms is essentially optimal.
BibTeX  Entry
@InProceedings{kumar_et_al:LIPIcs.SoCG.2022.52,
author = {Kumar, Neeraj and Lokshtanov, Daniel and Saurabh, Saket and Suri, Subhash and Xue, Jie},
title = {{Point Separation and Obstacle Removal by Finding and Hitting Odd Cycles}},
booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)},
pages = {52:152:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772273},
ISSN = {18688969},
year = {2022},
volume = {224},
editor = {Goaoc, Xavier and Kerber, Michael},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16060},
URN = {urn:nbn:de:0030drops160609},
doi = {10.4230/LIPIcs.SoCG.2022.52},
annote = {Keywords: pointsseparation, min color path, constraint removal, barrier resillience}
}
Keywords: 

pointsseparation, min color path, constraint removal, barrier resillience 
Collection: 

38th International Symposium on Computational Geometry (SoCG 2022) 
Issue Date: 

2022 
Date of publication: 

01.06.2022 