Cabello, S. and Giannopoulos, P. ORCID: 0000000262611961 (2016). The Complexity of Separating Points in the Plane. Algorithmica, 74(2), pp. 643663. doi: 10.1007/s0045301499656
Abstract
We study the following separation problem: given n connected curves and two points s and t in the plane, compute the minimum number of curves one needs to retain so that any path connecting s to t intersects some of the retained curves. We give the first polynomial (O(n3)) time algorithm for the problem, assuming that the curves have reasonable computational properties. The algorithm is based on considering the intersection graph of the curves, defining an appropriate family of closed walks in the intersection graph that satisfies the 3pathcondition, and arguing that a shortest cycle in the family gives an optimal solution. The 3pathcondition has been used mainly in topological graph theory, and thus its use here makes the connection to topology clear. We also show that the generalized version, where several input points are to be separated, is NPhard for natural families of curves, like segments in two directions or unit circles.
Publication Type:  Article 

Additional Information:  This is a postpeerreview, precopyedit version of an article published in Algorithmica. The final authenticated version is available online at: http://dx.doi.org/10.1007/s0045301499656. 
Publisher Keywords:  Point separation, 3Paths property, Connected curves, NPhardness 
Subjects:  Q Science > QA Mathematics Q Science > QA Mathematics > QA75 Electronic computers. Computer science 
Departments:  School of Mathematics, Computer Science & Engineering > Computer Science 
URI:  http://openaccess.city.ac.uk/id/eprint/21509 

Text
 Accepted Version
Download (404kB)  Preview 
Export
Downloads
Downloads per month over past year
Actions (login required)
Admin Login 