Arrow Research search

Author name cluster

Subhash Suri

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

37 papers
2 author rows

Possible papers

37

SODA Conference 2022 Conference Paper

Dynamic Geometric Set Cover, Revisited

  • Timothy M. Chan
  • Qizheng He
  • Subhash Suri
  • Jie Xue 0003

Geometric set cover is a classical problem in computational geometry, which has been extensively studied in the past. In the dynamic version of the problem, points and ranges may be inserted and deleted, and our goal is to efficiently maintain a set cover solution (satisfying certain quality requirement) for the dynamic problem instance. In this paper, we give a plethora of new dynamic geometric set cover data structures in 1D and 2D, which significantly improve and extend the previous results. Our results include the following: The first data structure for (1 + ∊ )-approximate dynamic interval set cover with polylogarithmic amortized update time. Specifically, we achieve an update time of O (log 3 n/∊ ), improving the O ( n δ / ∊ ) bound of Agarwal et al. [SoCG'20], where δ > 0 denotes an arbitrarily small constant. A data structure for O (1)-approximate dynamic unit-square set cover with amortized update time, substantially improving the O ( n 1/2+ δ ) update time of Agarwal et al. [SoCG'20]. A data structure for O (1)-approximate dynamic square set cover with O ( n 1/2+ δ ) randomized amortized update time, improving the O ( n 2/3+ δ ) update time of Chan and He [SoCG'21]. A data structure for O (1)-approximate dynamic 2D halfplane set cover with O ( n 17/23+ δ ) randomized amortized update time. The previous solution for halfplane set cover by Chan and He [SoCG'21] is slower and can only report the size of the approximate solution. The first sublinear results for the weighted version of dynamic geometric set cover. Specifically, we give a data structure for (3 + o (1))-approximate dynamic weighted interval set cover with amortized update time and a data structure for O (1)-approximate dynamic weighted unit-square set cover with O ( n δ ) amortized update time.

Details

IJCAI Conference 2022 Conference Paper

Multiwinner Elections under Minimax Chamberlin-Courant Rule in Euclidean Space

  • Chinmay Sonar
  • Subhash Suri
  • Jie Xue

We consider multiwinner elections in Euclidean space using the minimax Chamberlin-Courant rule. In this setting, voters and candidates are embedded in a d-dimensional Euclidean space, and the goal is to choose a committee of k candidates so that the rank of any voter's most preferred candidate in the committee is minimized. (The problem is also equivalent to the ordinal version of the classical k-center problem. ) We show that the problem is NP-hard in any dimension d >= 2, and also provably hard to approximate. Our main results are three polynomial-time approximation schemes, each of which finds a committee with provably good minimax score. In all cases, we show that our approximation bounds are tight or close to tight. We mainly focus on the 1-Borda rule but some of our results also hold for the more general r-Borda.

PDF Details DOI

SODA Conference 2021 Conference Paper

A Constant Factor Approximation for Navigating Through Connected Obstacles in the Plane

  • Neeraj Kumar 0004
  • Daniel Lokshtanov
  • Saket Saurabh 0001
  • Subhash Suri

Given two points s and t in the plane and a set of obstacles defined by closed curves, what is the minimum number of obstacles touched by a path connecting s and t? This is a fundamental and well-studied problem arising naturally in computational geometry, graph theory (under the names M in -C olor P ath and M inimum L abel P ath ), wireless sensor networks (B arrier R esilience ) and motion planning (M inimum C onstraint R emoval ). It remains NP-hard even for very simple-shaped obstacles such as unit-length line segments. In this paper we give the first constant factor approximation algorithm for this problem, resolving an open problem of [Chan and Kirkpatrick, TCS, 2014] and [Bandyapadhyay et al. , CGTA, 2020]. We also obtain a constant factor approximation for the M inimum C olor P rize C ollecting S teiner F orest where the goal is to connect multiple request pairs ( s 1, t 1 ), …, ( s k, t k ) while minimizing the number of obstacles touched by any ( s i, t i ) path plus a fixed cost of w i for each pair ( s i, t i ) left disconnected. This generalizes the classic S teiner F orest and P rize -C ollecting S teiner F orest problems on planar graphs, for which intricate PTASes are known. In contrast, no PTAS is possible for M in -C olor P ath even on planar graphs since the problem is known to be APX-hard [Eiben and Kanj, TALG, 2020]. Additionally, we show that generalizations of the problem to disconnected obstacles in the plane or connected obstacles in higher dimensions are strongly inapproximable assuming some well-known hardness conjectures.

Details

YNIMG Journal 2018 Journal Article

Analytic tractography: A closed-form solution for estimating local white matter connectivity with diffusion MRI

  • Matthew Cieslak
  • Tegan Brennan
  • Wendy Meiring
  • Lukas J. Volz
  • Clint Greene
  • Alexander Asturias
  • Subhash Suri
  • Scott T. Grafton

White matter structures composed of myelinated axons in the living human brain are primarily studied by diffusion-weighted MRI (dMRI). These long-range projections are typically characterized in a two-step process: dMRI signal is used to estimate the orientation of axon segments within each voxel, then these local orientations are linked together to estimate the spatial extent of putative white matter bundles. Tractography, the process of tracing bundles across voxels, either requires computationally expensive (probabilistic) simulations to model uncertainty in fiber orientation or ignores it completely (deterministic). Furthermore, simulation necessarily generates a finite number of trajectories, introducing “simulation error” to trajectory estimates. Here we introduce a method to analytically (via a closed-form solution) take an orientation distribution function (ODF) from each voxel and calculate the probabilities that a trajectory projects from a voxel into each directly adjacent voxels. We validate our method by demonstrating experimentally that probabilistic simulations converge to our analytically computed transition probabilities at the voxel level as the number of simulated seeds increases. We then show that our method accurately calculates the ground-truth transition probabilities from a publicly available phantom dataset. As a demonstration, we incorporate our analytic method for voxel transition probabilities into the Voxel Graph framework, creating a quantitative framework for assessing white matter structure, which we call “analytic tractography”. The long-range connectivity problem is reduced to finding paths in a graph whose adjacency structure reflects voxel-to-voxel analytic transition probabilities. We demonstrate that this approach performs comparably to the current most widely-used probabilistic and deterministic approaches at a fraction of the computational cost. We also demonstrate that analytic tractography works on multiple diffusion sampling schemes, reconstruction method or parameters used to define paths. Open source software compatible with popular dMRI reconstruction software is provided.

Details DOI

MFCS Conference 2018 Conference Paper

Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames

  • Sayan Bandyapadhyay
  • Anil Maheshwari
  • Saeed Mehrabi 0001
  • Subhash Suri

We consider the Minimum Dominating Set (MDS) problem on the intersection graphs of geometric objects. Even for simple and widely-used geometric objects such as rectangles, no sub-logarithmic approximation is known for the problem and (perhaps surprisingly) the problem is NP-hard even when all the rectangles are "anchored" at a diagonal line with slope -1 (Pandit, CCCG 2017). In this paper, we first show that for any epsilon>0, there exists a (2+epsilon)-approximation algorithm for the MDS problem on "diagonal-anchored" rectangles, providing the first O(1)-approximation for the problem on a non-trivial subclass of rectangles. It is not hard to see that the MDS problem on "diagonal-anchored" rectangles is the same as the MDS problem on "diagonal-anchored" L-frames: the union of a vertical and a horizontal line segment that share an endpoint. As such, we also obtain a (2+epsilon)-approximation for the problem with "diagonal-anchored" L-frames. On the other hand, we show that the problem is APX-hard in case the input L-frames intersect the diagonal, or the horizontal segments of the L-frames intersect a vertical line. However, as we show, the problem is linear-time solvable in case the L-frames intersect a vertical as well as a horizontal line. Finally, we consider the MDS problem in the so-called "edge intersection model" and obtain a number of results, answering two questions posed by Mehrabi (WAOA 2017).

Details

SODA Conference 2015 Conference Paper

Geometric k Shortest Paths

  • Sylvester David Eriksson-Bique
  • John Hershberger 0001
  • Valentin Polishchuk
  • Bettina Speckmann
  • Subhash Suri
  • Topi Talvitie
  • Kevin Verbeek
  • Hakan Yildiz

We consider the problem of computing k shortest paths in a two-dimensional environment with polygonal obstacles, where the j th path, for 1 ≤ j ≤ k, is the shortest path in the free space that is also homotopically distinct from each of the first j – 1 paths. In fact, we consider a more general problem: given a source point s, construct a partition of the free space, called the kth shortest path map ( k -SPM), in which the homotopy of the k th shortest path in a region has the same structure. Our main combinatorial result establishes a tight bound of Θ( k 2 h + kn ) on the worst-case complexity of this map. We also describe an O (( k 3 h + k 2 n ) log ( kn )) time algorithm for constructing the map. In fact, the algorithm constructs the j th map for every j ≤ k. Finally, we present a simple visibility-based algorithm for computing the k shortest paths between two fixed points. This algorithm runs in O ( m log n + k ) time and uses O ( m + k ) space, where m is the size of the visibility graph. This latter algorithm can be extended to compute k shortest simple (non-self-intersecting) paths, taking O ( k 2 m ( m + kn ) log ( kn )) time. We invite the reader to play with our applet demonstrating k -SPMs [10].

Details

TCS Journal 2014 Journal Article

k -Capture in multiagent pursuit evasion, or the lion and the hyenas

  • Shaunak D. Bopardikar
  • Subhash Suri

We consider the following generalization of the classical pursuit–evasion problem, which we call k-capture. A group of n pursuers (hyenas) wish to capture an evader (lion) who is free to move in an m-dimensional Euclidean space, the pursuers and the evader can move with the same maximum speed, and at least k pursuers must simultaneously reach the evaderʼs location to capture it. If fewer than k pursuers reach the evader, then those pursuers get destroyed by the evader. Under what conditions can the evader be k-captured? We study this problem in the discrete time, continuous space model and prove that k-capture is possible if and only if there exists a time when the evader lies in the interior of the pursuersʼ k-Hull. When the pursuit occurs inside a compact, convex subset of the Euclidean space, we show through an easy constructive strategy that k-capture is always possible.

Details DOI

AAAI Conference 2012 Conference Paper

Catch Me If You Can: Pursuit and Capture in Polygonal Environments with Obstacles

  • Kyle Klein
  • Subhash Suri

We resolve a several-years old open question in visibilitybased pursuit evasion: how many pursuers are needed to capture an evader in an arbitrary polygonal environment with obstacles? The evader is assumed to be adversarial, moves with the same maximum speed as pursuers, and is “sensed” by a pursuer only when it lies in line-of-sight of that pursuer. The players move in discrete time steps, and the capture occurs when a pursuer reaches the position of the evader on its move. Our main result is that O( √ h + log n) pursuers can always win the game with a deterministic search strategy in any polygon with n vertices and h obstacles (holes). In order to achieve this bound, however, we argue that the environment must satisfy a minimum feature size property, which essentially requires the minimum distance between any two vertices to be of the same order as the speed of the players. Without the minimum feature size assumption, we show that Ω( p n/ log n) pursuers are needed in the worst-case even for simply-connected (hole-free) polygons of n vertices! This reveals an unexpected subtlety that seems to have been overlooked in previous work claiming that O(log n) pursuers can always win in simply-connected n-gons. Our lower bound also shows that capturing an evader is inherently more difficult than just “seeing” it because O(log n) pursuers are provably sufficient for line-of-sight detection even against an arbitrarily fast evader in simple n-gons.

PDF Details

AAAI Conference 2011 Conference Paper

Complete Information Pursuit Evasion in Polygonal Environments

  • Kyle Klein
  • Subhash Suri

Suppose an unpredictable evader is free to move around in a polygonal environment of arbitrary complexity that is under full camera surveillance. How many pursuers, each with the same maximum speed as the evader, are necessary and sufficient to guarantee a successful capture of the evader? The pursuers always know the evader’s current position through the camera network, but need to physically reach the evader to capture it. We allow the evader the knowledge of the current positions of all the pursuers as well—this accords with the standard worst-case analysis model, but also models a practical situation where the evader has “hacked” into the surveillance system. Our main result is to prove that three pursuers are always sufficient and sometimes necessary to capture the evader. The bound is independent of the number of vertices or holes in the polygonal environment.

PDF Details

AAAI Conference 2007 Conference Paper

Simple Robots with Minimal Sensing: From Local Visibility to Global Geometry

  • Subhash Suri

We consider problems of geometric exploration and selfdeployment for simple robots that can only sense the combinatorial (non-metric) features of their surroundings. Even with such a limited sensing, we show that robots can achieve complex geometric reasoning and perform many non-trivial tasks. Specifically, we show that one robot equipped with a single pebble can decide whether the workspace environment is a simply-connected polygon and, if not, it can also count the number of holes in the environment. Highlighting the subtleties of our sensing model, we show that a robot can decide whether the environment is a convex polygon, yet it cannot resolve whether a particular vertex is convex. Finally, we show that using such local and minimal sensing, a robot can compute a proper triangulation of a polygon, and that the triangulation algorithm can be implemented collaboratively by a group of m such robots, each with Θ(n/m) memory. As a corollary of the triangulation algorithm, we derive a distributed analog of the well-known Art Gallery Theorem: a group of n/3 (bounded memory) robots in our minimal sensing model can self-deploy to achieve visibility coverage of an n-vertex art gallery (polygon). This resolves an open question raised recently by Ganguli et al.

PDF Details

AIJ Journal 2003 Journal Article

BOB: Improved winner determination in combinatorial auctions and generalizations

  • Tuomas Sandholm
  • Subhash Suri

Combinatorial auctions can be used to reach efficient resource and task allocations in multiagent systems where the items are complementary or substitutable. Determining the winners is NP -complete and inapproximable, but it was recently shown that optimal search algorithms do very well on average. This paper presents a more sophisticated search algorithm for optimal (and anytime) winner determination, including structural improvements that reduce search tree size, faster data structures, and optimizations at search nodes based on driving toward, identifying and solving tractable special cases. We also uncover a more general tractable special case, and design algorithms for solving it as well as for solving known tractable special cases substantially faster. We generalize combinatorial auctions to multiple units of each item, to reserve prices on singletons as well as combinations, and to combinatorial exchanges. All of these generalizations support both complementarity and substitutability of the items. Finally, we present algorithms for determining the winners in these generalizations.

Details DOI

FOCS Conference 2001 Conference Paper

Vickrey Prices and Shortest Paths: What is an Edge Worth?

  • John Hershberger 0001
  • Subhash Suri

We solve a shortest path problem that is motivated by recent interest in pricing networks or other computational resources. Informally, how much is an edge in a network worth to a user who wants to send data between two nodes along a shortest path? If the network is a decentralized entity, such as the Internet, in which multiple self-interested agents own different parts of the network, then auction-based pricing seems appropriate. A celebrated result from auction theory shows that the use of Vickrey pricing motivates the owners of the network resources to bid truthfully. In Vickrey's scheme, each agent is compensated in proportion to the marginal utility he brings to the auction. In the context of shortest path routing, an edge's utility is the value by which it lowers the length of the shortest path, i. e. , the difference between the shortest path lengths with and without the edge. Our problem is to compute these marginal values for all the edges of the network efficiently. The naive method requires solving the single-source shortest path problem up to n times, for an n-node network. We show that the Vickrey prices for all the edges can be computed in the same asymptotic time complexity as one single-source shortest path problem. This solves an open problem posed by N. Nisan and A. Ronen (1999).

Details

TCS Journal 1994 Journal Article

Data structures for two-edge connectivity in planar graphs

  • John Hershberger
  • Monika Rauch
  • Subhash Suri

We present a data structure for maintaining 2-edge connectivity information dynamically in an embedded planar graph. The data structure requires linear storage and preprocessing time for its construction, supports online updates (deletion of an edge or insertion of an edge consistent with the embedding) in O(log2 n) time, and answers a query (whether two vertices are in the same 2-edge-connected component) in O(log n) time. The previous best algorithm for this problem requires O(log3 n) time for updates.

Details DOI

FOCS Conference 1993 Conference Paper

Efficient Computation of Euclidean Shortest Paths in the Plane

  • John Hershberger 0001
  • Subhash Suri

We propose a new algorithm for a classical problem in plane computational geometry: computing a shortest path between two points in the presence of polygonal obstacles. Our algorithm runs in worst-case time O(nlog/sup 2/ n) and requires O(nlog n) space, where n is the total number of vertices in the obstacle polygons. Our algorithm actually computes a planar map that encodes shortest paths from a fixed source point to all other points of the plane; the map can be used to answer single-source shortest path queries in O(log n) time. The time complexity of our algorithm is a significant improvement over all previous results known for the shortest path problem. >

Details

FOCS Conference 1989 Conference Paper

Dynamically Computing the Maxima of Decomposable Functions, with Applications

  • David P. Dobkin
  • Subhash Suri

The authors present a general technique for updating the maximum (minimum) value of a decomposable function as elements are inserted into and deleted from the set S. Applications of this technique include efficient algorithms for dynamically computing the diameter or closest pair of a set of points, minimum separation among a set of rectangles, smallest distance between a set of points and a set of hyperplanes, and largest or smallest area (perimeter) rectangles determined by a set of points. The main appeal of the approach lies in its generality. Several research directions suggested by the work are noted. >

Details

FOCS Conference 1989 Conference Paper

Fast Matching Algorithms for Points on a Polygon (Extended Abstract)

  • Odile Marcotte
  • Subhash Suri

The complete graph induced by a set of 2n points on the boundary of a polygon is considered. The edges are assigned weights equal to the Euclidean distance between their endpoints if the endpoints see each other in the polygon, and + infinity otherwise. An O(n log n)-time algorithm is obtained for finding a minimum-weight perfect matching in this graph if the polygon is convex, and an O(n log/sup 2/n)-time algorithm if the polygon is simple but nonconvex. The assignment problem for a convex polygon is solved in time O(n log n), and O(n alpha (n)) and O(n alpha (n) log n) time bounds are obtained for the verification problem on convex and nonconvex polygons, respectively, where alpha (n) is the functional inverse of the Ackermann function. >

Details

I&C Journal 1989 Journal Article

Finding minimal convex nested polygons

  • Alok Aggarwal
  • Heather Booth
  • Joseph O'Rourke
  • Subhash Suri
  • Chee K. Yap

We consider the problem of finding a polygon nested between two given convex polygons that has a minimal number of vertices. Our main result is an O(n log k) algorithm for solving the problem, where n is the total number of vertices of the given polygons, and k is the number of vertices of a minimal nested polygon. We also present an O(n) sub-optimal algorithm, and a simple O(nk) optimal algorithm.

Details DOI
v2026.09.13