Journal article
Improved approximation bounds for the minimum constraint removal problem
Computational geometry : theory and applications, Vol.90, p.101650
10/01/2020
DOI: 10.1016/j.comgeo.2020.101650
Abstract
In the minimum constraint removal problem, we are given a set of overlapping geometric objects as obstacles in the plane, and we want to find the minimum number of obstacles that must be removed to reach a target point t from the source point s by an obstacle-free path. The problem is known to be intractable and no sub-linear approximations are known even for simple obstacles such as rectangles and disks. The main result of our paper is an approximation framework that gives an O(root n alpha(n))-approximation for polygonal obstacles, where alpha(n) denotes the inverse Ackermann's function. For pseudodisks and rectilinear polygons, the same technique achieves an O(root n)-approximation. The technique also gives O(root n)-approximation for the minimum color pathproblem in graphs. We also present some inapproximability results for the geometric constraint removal problem. (C) 2020 Elsevier B.V. All rights reserved.
Details
- Title: Subtitle
- Improved approximation bounds for the minimum constraint removal problem
- Creators
- Sayan Bandyapadhyay - University of IowaNeeraj Kumar - University of California, Santa BarbaraSubhash Suri - University of California, Santa BarbaraKasturi Varadarajan - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Computational geometry : theory and applications, Vol.90, p.101650
- DOI
- 10.1016/j.comgeo.2020.101650
- ISSN
- 0925-7721
- eISSN
- 1879-081X
- Publisher
- Elsevier
- Number of pages
- 11
- Grant note
- CCF1525817; CCF-1814172; CCF-1615845 / National Science Foundation; National Science Foundation (NSF)
- Language
- English
- Date published
- 10/01/2020
- Academic Unit
- Computer Science
- Record Identifier
- 9984259488402771
Metrics
6 Record Views