skip to main content

Attention:

The NSF Public Access Repository (PAR) system and access will be unavailable from 11:00 PM ET on Thursday, February 13 until 2:00 AM ET on Friday, February 14 due to maintenance. We apologize for the inconvenience.


Search for: All records

Creators/Authors contains: "Bandyapadhyay, S"

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. 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(√nα(n))-approximation for polygonal obstacles, where α(n) denotes the inverse Ackermann’s function. For pseudodisks and rectilinear polygons, the same technique achieves an O(√n)-approximation. The technique also gives O (√n)-approximation for the minimum color path problem in graphs. We also present some inapproximability results for the geometric constraint removal problem. 
    more » « less