2026-07-23T22:31:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24559 2025-12-16T14:00:49Z ddc:004 open_access

Separating Two Points with Obstacles in the Plane: Improved Upper and Lower Bounds Spalding-Jamieson, Jack Naredla, Anurag Murty obstacle separation point separation geometric intersection graph Z₂-homology fine-grained lower bounds Given two points in the plane, and a set of "obstacles" given as curves through the plane with assigned weights, we consider the point-separation problem, which asks for a minimum-weight subset of the obstacles separating the two points. A few computational models for this problem have been previously studied. We give a unified approach to this problem in all models via a reduction to a particular shortest-path problem, and obtain improved running times in essentially all cases. In addition, we also give fine-grained lower bounds for many cases. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jack Spalding-Jamieson and Anurag Murty Naredla 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.90 urn:nbn:de:0030-drops-245598 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.90 eng https://creativecommons.org/licenses/by/4.0/legalcode