Arrow Research search

Author name cluster

Pankaj K. Agarwal

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.

60 papers
2 author rows

Possible papers

60

ICML Conference 2025 Conference Paper

De-coupled NeuroGF for Shortest Path Distance Approximations on Large Terrain Graphs

  • Samantha Chen 0001
  • Pankaj K. Agarwal
  • Yusu Wang 0001

The ability to acquire high-resolution, large-scale geospatial data at an unprecedented using LiDAR and other related technologies has intensified the need for scalable algorithms for terrain analysis, including shortest-path-distance (SPD) queries on large-scale terrain digital elevation models (DEMs). In this paper, we present a neural data structure for efficiently answering SPD queries approximately on a large terrain DEM, which is based on the recently proposed neural geodesic field (NeuroGF) framework (Zhang et al. , 2023)—the state-of-the-art neural data structure for estimating geodesic distance. In particular, we propose a decoupled-NeuroGF data structure combined with an efficient two-stage mixed-training strategy, which significantly reduces computational bottlenecks and enables efficient training on terrain DEMs at a scale not feasible before. We demonstrate the efficacy of our approach by performing detailed experiments on both synthetic and real data sets. For instance, we can train a small model with around 70000 parameters on a terrain DEM with 16 million nodes in a matter of hours that can answer SPD queries with 1% relative error in at most 10ms per query.

Details

NeurIPS Conference 2024 Conference Paper

A Combinatorial Algorithm for the Semi-Discrete Optimal Transport Problem

  • Pankaj K. Agarwal
  • Sharath Raghvendra
  • Pouyan Shirzadian
  • Keegan Yao

Optimal Transport (OT, also known as the Wasserstein distance) is a popular metric for comparing probability distributions and has been successfully used in many machine-learning applications. In the semi-discrete $2$-Wasserstein problem, we wish to compute the cheapest way to transport all the mass from a continuous distribution $\mu$ to a discrete distribution $\nu$ in $\mathbb{R}^d$ for $d\ge 1$, where the cost of transporting unit mass between points $a$ and $b$ is $d(a, b)=||a-b||^2$. When both distributions are discrete, a simple combinatorial framework has been used to find the exact solution (see e. g. [Orlin, STOC 1988]). In this paper, we propose a combinatorial framework for the semi-discrete OT, which can be viewed as an extension of the combinatorial framework for the discrete OT but requires several new ideas. We present a new algorithm that given $\mu$ and $\nu$ in $\mathbb{R}^2$ and a parameter $\varepsilon>0$, computes an $\varepsilon$-additive approximate semi-discrete transport plan in $O(n^{4}\log n\log \frac{1}{\varepsilon})$ time (in the worst case), where $n$ is the support-size of the discrete distribution $\nu$ and we assume that the mass of $\mu$ inside a triangle can be computed in $O(1)$ time. Our algorithm is significantly faster than the known algorithms, and unlike many numerical algorithms, it does not make any assumptions on the smoothness of $\mu$. As an application of our algorithm, we describe a data structure to store a large discrete distribution $\mu$ (with support size $N$) using $O(N)$ space so that, given a query discrete distribution $\nu$ (with support size $k$), an $\varepsilon$-additive approximate transport plan can be computed in $O(k^{3}\sqrt{N}\log \frac{1}{\varepsilon})$ time in $2$ dimensions. Our algorithm and data structure extend to higher dimensions as well as to $p$-Wasserstein problem for any $p \ge 1$.

PDF Details DOI

SODA Conference 2024 Conference Paper

Fast and Accurate Approximations of the Optimal Transport in Semi-Discrete and Discrete Settings

  • Pankaj K. Agarwal
  • Sharath Raghvendra
  • Pouyan Shirzadian
  • Keegan Yao

Given a d -dimensional continuous (resp. discrete) probability distribution μ and a discrete distribution ν, the semi-discrete (resp. discrete) optimal transport (OT) problem asks for computing a minimum-cost plan to transport mass from μ to ν; we assume n to be the number of points in the support of the discrete distributions. In this paper, we present three approximation algorithms for the OT problem with strong provable guarantees. (i) Additive approximation for semi-discrete OT: For any parameter ɛ > 0, we present an algorithm that computes a semi-discrete transport plan with cost in time; here, τ* is the optimal transport plan, D is the diameter of the supports of μ and ν, and we assume we have access to an oracle that outputs the mass of μ inside a constant-complexity region in O (1) time. Our algorithm works for several ground distances including the L p -norm and the squared-Euclidean distance. (ii) Relative approximation for semi-discrete OT: For any parameter ɛ > 0, we present an algorithm that computes a semi-discrete transport plan with cost in n log( n ) · (ɛ -1 log log n ) O ( d ) expected time; here, τ* is the optimal transport plan, and we assume we have access to an oracle that outputs the mass of μ inside an orthogonal box in O (1) time, and the ground distance is any L p norm. (iii) Relative approximation for discrete OT: For any parameter ɛ > 0, we present a Monte-Carlo algorithm that computes a transport plan τ with an expected cost under any L p norm in n log( n ) · (ɛ -1 log log n ) O(d ) time; here, τ* is an optimal transport plan and we assume that the spread of the supports of μ and ν is polynomially bounded. * The full version of the paper can be accessed at https: //arxiv. org/abs/2311. 02172

Details

SODA Conference 2024 Conference Paper

Fast Approximation Algorithms for Piercing Boxes by Points

  • Pankaj K. Agarwal
  • Sariel Har-Peled
  • Rahul Raychaudhury
  • Stavros Sintos

Let B = (b 1, …, b n } be a set of n axis-aligned boxes in ℝ d where d ≥ 2 is a constant. The piercing problem is to compute a smallest set of points N ∪ ℝ d that hits every box in B, i. e. , N ∩ b i ≠ ϕ, for i = 1, …, n. The problem is known to be NP-Hard. Let p: = p ( B ), the piercing number be the minimum size of a piercing set of B. We first present a randomized O (log log p )-approximation algorithm with expected running time O ( n d/2 polylog( n )). Next, we show that the expected running time can be improved to near-linear using a sampling-based technique, if p = O ( n 1/( d -1) ). Specifically, in the plane, the improved running time is O(n log p ), assuming p < n / log Ω(1) n. Finally, we study the dynamic version of the piercing problem where boxes can be inserted or deleted. For boxes in ℝ 2, we obtain a randomized O (log log p )-approximation algorithm with O ( n 1/2 polylog( n )) amortized expected update time for insertion or deletion of boxes. For squares in ℝ 2, the update time can be improved to O ( n 1/3 polylog( n )). Our algorithms are based on the multiplicative weight-update (MWU) method and require the construction of a weak ɛ -net for a point set with respect to boxes. A key idea of our work is to exploit the duality between the piercing set and independent set (for boxes) to speed up our MWU. We also present a simpler and slightly more efficient algorithm for constructing a weak ɛ -net than in [Ezr10], which is of independent interest. Our approach also yields a simpler algorithm for constructing (regular) ɛ -nets with respect to boxes for d =2, 3. * A full version of this paper is available on the arXiv [AHRS23].

Details

SODA Conference 2024 Conference Paper

Vertical Decomposition in 3D and 4D with Applications to Line Nearest-Neighbor Searching in 3D

  • Pankaj K. Agarwal
  • Esther Ezra
  • Micha Sharir

Vertical decomposition is a widely used general technique for decomposing the cells of arrangements of semi-algebraic sets in ℝ d into constant-complexity subcells. In this paper, we settle in the affirmative a few long-standing open problems involving the vertical decomposition of substructures of arrangements for d = 3, 4: (i) Let S be a collection of n semi-algebraic sets of constant complexity in ℝ 3, and let U ( m ) be an upper bound on the complexity of the union U ( S ‘) of any subset S’ ⊆ S of size at most m. We prove that the complexity of the vertical decomposition of the complement of U ( S ) is O * ( n 2 + U ( n )) (where the O * (·) notation hides subpolynomial factors). We also show that the complexity of the vertical decomposition of the entire arrangement A ( S ) is O*(n 2 + X ), where X is the number of vertices in A ( S ). (ii) Let F be a collection of n trivariate functions whose graphs are semi-algebraic sets of constant complexity. We show that the complexity of the vertical decomposition of the portion of the arrangement A ( F ) in ℝ 4 lying below the lower envelope of F is O *( n 3 ). These results lead to efficient algorithms for a variety of problems involving these decompositions, including algorithms for constructing the decompositions themselves, and for constructing (1/ r )-cuttings of substructures of arrangements of the kinds considered above. One additional algorithm of interest is for output-sensitive point enclosure queries amid semi-algebraic sets in three or four dimensions. In addition, as a main domain of applications, we study various proximity problems involving points and lines in ℝ 3: We first present a linear-size data structure for answering nearest-neighbor queries, with points, amid n lines in ℝ 3 in O *( n 2/3 ) time per query. We also study the converse problem, where we return the nearest neighbor of a query line amid n input points, or lines, in ℝ 3. We obtain a data structure of O *( n 4 ) size that answers a nearest-neighbor query in O (log n ) time. * Work by Pankaj Agarwal has been partially supported by NSF grants IIS-18-14493, CCF-20-07556, and CCF-22-23870. Work by Esther Ezra has been partially supported by Israel Science Foundation Grant 800/22, and also by US-Israel Binational Science Foundation under Grant 2022131. Work by Micha Sharir has been partially supported by Israel Science Foundation Grant 260/18.

Details

ICLR Conference 2023 Conference Paper

A Higher Precision Algorithm for Computing the $1$-Wasserstein Distance

  • Pankaj K. Agarwal
  • Sharath Raghvendra
  • Pouyan Shirzadian
  • Rachita Sowle

We consider the problem of computing the $1$-Wasserstein distance $\mathcal{W}(\mu,\nu)$ between two $d$-dimensional discrete distributions $\mu$ and $\nu$ whose support lie within the unit hypercube. There are several algorithms that estimate $\mathcal{W}(\mu,\nu)$ within an additive error of $\varepsilon$. However, when $\mathcal{W}(\mu,\nu)$ is small, the additive error $\varepsilon$ dominates, leading to noisy results. Consider any additive approximation algorithm with execution time $T(n,\varepsilon)$. We propose an algorithm that runs in $O(T(n,\varepsilon/d) \log n)$ time and boosts the accuracy of estimating $\mathcal{W}(\mu,\nu)$ from $\varepsilon$ to an expected additive error of $\min\{\varepsilon, (d\log_{\sqrt{d}/\varepsilon} n)\mathcal{W}(\mu,\nu)\}$. For the special case where every point in the support of $\mu$ and $\nu$ has a mass of $1/n$ (also called the Euclidean Bipartite Matching problem), we describe an algorithm to boost the accuracy of any additive approximation algorithm from $\varepsilon$ to an expected additive error of $\min\{\varepsilon, (d\log\log n)\mathcal{W}(\mu,\nu)\}$ in $O(T(n, \varepsilon/d)\log\log n)$ time.

Details

STOC Conference 2022 Conference Paper

Deterministic, near-linear ε -approximation algorithm for geometric bipartite matching

  • Pankaj K. Agarwal
  • Hsien-Chih Chang
  • Sharath Raghvendra
  • Allen Xiao

Given two point sets A and B in ℝ d of size n each, for some constant dimension d ≥ 1, and a parameter ε>0, we present a deterministic algorithm that computes, in n ·(ε −1 log n ) O ( d ) time, a perfect matching between A and B whose cost is within a (1+ε) factor of the optimal matching under any ℓ p -norm. Although a Monte-Carlo algorithm with a similar running time is proposed by Raghvendra and Agarwal [J. ACM 2020], the best-known deterministic ε-approximation algorithm takes Ω( n 3/2 ) time. Our algorithm constructs a (refinement of a) tree cover of ℝ d , and we develop several new tools to apply a tree-cover based approach to compute an ε-approximate perfect matching.

Details

AAAI Conference 2022 Conference Paper

Locally Fair Partitioning

  • Pankaj K. Agarwal
  • Shao-Heng Ko
  • Kamesh Munagala
  • Erin Taylor

We model the societal task of redistricting political districts as a partitioning problem: Given a set of n points in the plane, each belonging to one of two parties, and a parameter k, our goal is to compute a partition Π of the plane into regions so that each region contains roughly σ = n/k points. Π should satisfy a notion of “local” fairness, which is related to the notion of core, a well-studied concept in cooperative game theory. A region is associated with the majority party in that region, and a point is unhappy in Π if it belongs to the minority party. A group D of roughly σ contiguous points is called a deviating group with respect to Π if majority of points in D are unhappy in Π. The partition Π is locally fair if there is no deviating group with respect to Π. This paper focuses on a restricted case when points lie in 1D. The problem is non-trivial even in this case. We consider both adversarial and “beyond worst-case” settings for this problem. For the former, we characterize the input parameters for which a locally fair partition always exists; we also show that a locally fair partition may not exist for certain parameters. We then consider input models where there are “runs” of red and blue points. For such clustered inputs, we show that a locally fair partition may not exist for certain values of σ, but an approximate locally fair partition exists if we allow some regions to have smaller sizes. We finally present a polynomialtime algorithm for computing a locally fair partition if one exists.

PDF Details

SODA Conference 2021 Conference Paper

Decomposing the Complement of the Union of Cubes in Three Dimensions

  • Pankaj K. Agarwal
  • Micha Sharir
  • Alex Steiger

Let be a set of n axis-aligned cubes of arbitrary sizes in ℝ 3 in general position. Let ≔ ( ) be their union, and let κ be the number of vertices on ∂; κ can vary between O (1) and O ( n 2 ). We show that cl(ℝ 3 \ ) can be decomposed into O ( κ log 4 n ) axis-aligned boxes with pairwise-disjoint interiors. Given a boundary representation of, such a decomposition can be computed in O ( n log 2 n + κ log 6 n ) time. We also show that a decomposition of size O (σ log 4 n + κ log 2 n ), where σ is the number of input cubes that appear on ∂, can be computed in O ( n log 2 n + σ log 8 n + κ log 6 n ) time. The complexity and runtime bounds improve to O ( n log n ) if all cubes in are congruent.

Details

SODA Conference 2021 Conference Paper

On Two-Handed Planar Assembly Partitioning with Connectivity Constraints

  • Pankaj K. Agarwal
  • Boris Aronov
  • Tzvika Geft
  • Dan Halperin

Assembly planning is a fundamental problem in robotics and automation, which aims to design a sequence of motions that brings the separate constituent parts of a product into their final placement in the product. It is convenient to study assembly planning in reverse order, where the following key problem, assembly partitioning, arises: Given a set of parts in their final placement in a product, partition them into two sets, each regarded as a rigid body, which we call a subassembly, such that these two subassemblies can be moved sufficiently far away from each other, without colliding with one another. The basic assembly planning problem is further complicated by practical consideration such as how to hold the parts in a subassembly together. Therefore, a desired property of a valid assembly partition is for each of the two subassemblies to be connected. In this paper we study a natural special case of the connected-assembly-partitioning problem: Given a connected set A of unit-grid squares in the plane, find a connected subset S ⊂ A such that A \ S is also connected and S can be rigidly translated to infinity along a prescribed direction without colliding with A\S. We show that even this simple problem is NP-complete, settling an open question posed by Wilson et al. a quarter of a century ago [16]. We complement the hardness result with two positive results. First, we show that the problem is fixed-parameter tractable and present an O (2 k n 2 )-time algorithm, where n = | A| and k = |S|. Second, we describe a special case of this problem where a connected partition can always be found in O ( n ) time.

Details

SODA Conference 2016 Conference Paper

An Efficient Algorithm for Computing High-Quality Paths amid Polygonal Obstacles

  • Pankaj K. Agarwal
  • Kyle Fox
  • Oren Salzman

We study a path-planning problem amid a set ℴ of obstacles in ℝ 2, in which we wish to compute a short path between two points while also maintaining a high clearance from ℴ; the clearance of a point is its distance from a nearest obstacle in ℴ. Specifically, the problem asks for a path minimizing the reciprocal of the clearance integrated over the length of the path. We present the first polynomial-time approximation scheme for this problem. Let n be the total number of obstacle vertices and let ∊ ∊ (0, 1]. Our algorithm computes in time a path of total cost at most (1 + ∊ ) times the cost of the optimal path.

Details

ICML Conference 2016 Conference Paper

Markov-modulated Marked Poisson Processes for Check-in Data

  • Jiangwei Pan
  • Vinayak A. Rao
  • Pankaj K. Agarwal
  • Alan E. Gelfand

We develop continuous-time probabilistic models to study trajectory data consisting of times and locations of user “check-ins”. We model the data as realizations of a marked point process, with intensity and mark-distribution modulated by a latent Markov jump process (MJP). We also include user-heterogeneity in our model by assigning each user a vector of “preferred locations”. Our model extends latent Dirichlet allocation by dropping the bag-of-words assumption and operating in continuous time. We show how an appropriate choice of priors allows efficient posterior inference. Our experiments demonstrate the usefulness of our approach by comparing with various baselines on a variety of tasks.

Details

STOC Conference 2014 Conference Paper

Approximation algorithms for bipartite matching with metric and geometric costs

  • Pankaj K. Agarwal
  • Sharath Raghvendra

Let G = G( A ∪ B,A × B ), with | A | = | B | = n , be a weighted bipartite graph, and let d(·,·) be the cost function on the edges. Let w( M ) denote the weight of a matching in G, and M * a minimum-cost perfect matching in G. We call a perfect matching M c-approximate , for c ≥ 1, if w( M ) ≤ c · w( M *). We present three approximation algorithms for computing minimum-cost perfect matchings in G. First, we consider the case when d(·,·) is a metric. For any δ > 0, we present an algorithm that, in O ( n 2+ δ log n log 2 (1/ δ )) time, computes a O (1/ δ α )-approximate matching of G, where α = log 3 2 ≈ 0.631. Next, we assume the existence of a dynamic data structure for answering approximate nearest neighbor (ANN) queries under d(··). Given two parameters ε, &delta ∈ (0, 1), we present an algorithm that, in O ( ε ---2 n 1+ δ τ ( n, ε ) log 2 ( n/ε ) log(1/ δ )) time, computes a O (1/ δ α )-approximate matching of G, where α = 1 + log 2 (1 + ε ) and τ ( n; ε ) is the query and update time of an ( ε /2)-ANN data structure. Finally, we present an algorithm that works even if d(·,·) is not a metric but admits an ANN data structure for d(·,·). In particular, we present an algorithm that computes, in O ( ε ---1 n 3/2 τ ( n, ε ) log 4 ( n / ε ) log Δ) time, a (1 + ε )-approximate matching of A and B ; here Δ is the ratio of the largest to the smallest-cost edge in G, and τ ( n, ε ) is the query and update time of an ( ε / c )-ANN data structure for some constant c > 1. We show that our results lead to faster matching algorithms for many geometric settings.

Details

SODA Conference 2013 Conference Paper

Computing the Discrete Fréchet Distance in Subquadratic Time

  • Pankaj K. Agarwal
  • Rinat Ben Avraham
  • Haim Kaplan
  • Micha Sharir

The Fréchet distance is a similarity measure between two curves A and B that takes into account the location and ordering of the points along the two curves: Informally, it is the minimum length of a leash required to connect a dog, walking along A, and its owner, walking along B, as they walk without backtracking along their respective curves from one endpoint to the other. The discrete Fréchet distance replaces the dog and its owner by a pair of frogs that can only reside on n and m specific stones on the curves A and B, respectively. These frogs hop from one stone to the next without backtracking, and the discrete Fréchet distance is the minimum length of a “leash” that connects the frogs and allows them to execute such a sequence of hops. It can be computed in quadratic time by a straightforward dynamic programming algorithm. We present the first subquadratic algorithm for computing the discrete Fréchet distance between two sequences of points in the plane. Assuming m ≤ n, the algorithm runs in time, in the standard RAM model, using O ( n ) storage. Our approach uses the geometry of the problem in a subtle way to encode legal positions of the frogs as states of a finite automaton.

Details

ICRA Conference 2013 Conference Paper

Sparsification of motion-planning roadmaps by edge contraction

  • Doron Shaharabani
  • Oren Salzman
  • Pankaj K. Agarwal
  • Dan Halperin

We present Roadmap Sparsification by Edge Contraction (RSEC), a simple and effective algorithm for reducing the size of a motion-planning roadmap. The algorithm exhibits minimal effect on the quality of paths that can be extracted from the new roadmap. The primitive operation used by RSEC is edge contraction-the contraction of a roadmap edge to a single vertex and the connection of the new vertex to the neighboring vertices of the contracted edge. For certain scenarios, we compress more than 98% of the edges and vertices at the cost of degradation of average shortest path length by at most 2%.

Details

STOC Conference 2012 Conference Paper

A near-linear time ε-approximation algorithm for geometric bipartite matching

  • Sharath Raghvendra
  • Pankaj K. Agarwal

For point sets A,B ⊂ R d , |A|=|B|=n, and for a parameter ε > 0, we present an algorithm that computes, in O(n poly(log n, 1/ε)) time, an ε-approximate perfect matching of A and B with high probability; the previously best known algorithm takes Ω(n 3/2 ) time. We approximate the L p -norm using a distance function, d(•,•) based on a randomly shifted quad-tree. The algorithm iteratively generates an approximate minimum-cost augmenting path under d(•,•) in time proportional to the length of the path. We show that the total length of the augmenting paths generated by the algorithm is O((n/ε)log n), implying that the running time of our algorithm is O(n poly(log n,1/ε)).

Details

SODA Conference 2012 Conference Paper

Algorithms for the transportation problem in geometric settings

  • Sharath Raghvendra
  • Pankaj K. Agarwal

For A, B ⊂ ℝ d, | A | + | B | = n, let a ∊ A have a demand d a ∊ ℤ + and b ∊ B have a supply s b ∊ ℤ +, σ a ∊ A d a = σ b ∊ B s b = U and let d(·, ·) be a distance function. Suppose the diameter of A ∪ B is Δ under d(·, ·), and ε > 0 is a parameter. We present an algorithm that in O (( n√U log 2 n + U log U ) Φ ( n ) log(Δ U /ε)) time computes a solution to the transportation problem on A, B which is within an additive error ε from the optimal solution. Here Φ( n ) is the query and update time of a dynamic weighted nearest neighbor data structure under distance function d(·, ·). Note that the (1/ε) appears only in the log term. As among various consequences we obtain, • For A, B ⊂ ℝ d and for the case where d(·, ·) is a metric, an ε-approximation algorithm for the transportation problem in O (( n √log 2 n + U log U ) Φ( n ) log ( U/ε )) time. • For A, B ⊂ [Δ] d and the L 1 and L ∞ distance, exact algorithm for computing an optimal bipartite matching of A, B that runs in O ( n 3/2 log d + Q (1) n log Δ) time. • For A, B ⊂ [Δ] 2 and RMS distance, exact algorithm for computing an optimal bipartite matching of A, B that runs in O ( n 3/2 + δ log Δ) time, for an arbitrarily small constant δ > 0. For point sets, A, B ⊂ [Δ], for the L p norm and for 0 < α, β < 1, we present a randomized dynamic data structure that maintains a partial solution to the transportation problem under insertions and deletions of points in which at least (1 − α) U of the demands are satisfied and whose cost is within (1 + β) of that of the optimal (complete) solution to the transportation problem with high probability. The insertion, deletion and update times are O (poly(log( n Δ)/αβ)), provided U = n O (1).

Details

FOCS Conference 2012 Conference Paper

On Range Searching with Semialgebraic Sets II

  • Pankaj K. Agarwal
  • Jirí Matousek 0001
  • Micha Sharir

Let $P$ be a set of $n$ points in $\R^d$. We present a linear-size data structure for answering range queries on $P$ with constant-complexity semi algebraic sets as ranges, in time close to $O(n^{1-1/d})$. It essentially matches the performance of similar structures for simplex range searching, and, for $d\ge 5$, significantly improves earlier solutions by the first two authors obtained in~1994. This almost settles a long-standing open problem in range searching. The data structure is based on the polynomial-partitioning technique of Guth and Katz [arXiv: 1011. 4105], which shows that for a parameter $r$, $1

Details

ICRA Conference 2003 Conference Paper

HPRM: a hierarchical PRM

  • Anne D. Collins
  • Pankaj K. Agarwal
  • John Harer

We introduce a hierarchical variant of the probabilistic roadmap method for motion planning. By recursively refining an initially sparse sampling in neighborhoods of the obstacle boundary, our algorithm generates a smaller roadmap that is more likely to find narrow passages than uniform sampling. We analyze the failure probability and computation time, relating them to path length, path clearance, roadmap size, recursion depth, and a local property of the free space. The approach is general, and can be tailored to any variety of robots. In particular, we describe algorithmic details for a planar articulated arm.

Details

ICRA Conference 2001 Conference Paper

Minimal Trap Design

  • Pankaj K. Agarwal
  • Anne D. Collins
  • John Harer

This paper addresses the issue of trap design for sensorless automated assembly. First, we present a simple algorithm that determines in O(nm /spl alpha/(nm) log(nm)) time whether an n-sided polygonal part will fall through an m-sided polygonal trap. We then introduce the notion of a minimal trap for a polygonal part, and develop an algorithm to design a family of minimal feeders built from these traps. The algorithm runs in O(kn/sup 3+/spl epsiv//) time, where k is the number of stable orientations of P. Moreover, it is complete in the sense that we can always find a feeder, provided that one exists that rejects and supports the appropriate poses of the part.

Details

FOCS Conference 2001 Conference Paper

On the Complexity of Many Faces in Arrangements of Circles

  • Pankaj K. Agarwal
  • Boris Aronov
  • Micha Sharir

We obtain improved bounds on the complexity of m distinct faces in an arrangement of n circles and in an arrangement of n unit circles. The bounds are worst-case tight for unit circles, and, for general circles, they nearly coincide with the best known bounds for the number of incidences between m points and n circles.

Details

FOCS Conference 1998 Conference Paper

Parametric and Kinetic Minimum Spanning Trees

  • Pankaj K. Agarwal
  • David Eppstein
  • Leonidas J. Guibas
  • Monika Henzinger

We consider the parametric minimum spanning tree problem, in which we are given a graph with edge weights that are linear functions of a parameter /spl lambda/ and wish to compute the sequence of minimum spanning trees generated as /spl lambda/ varies. We also consider the kinetic minimum spanning tree problem, in which /spl lambda/ represents time and the graph is subject in addition to changes such as edge insertions, deletions, and modifications of the weight functions as time progresses. We solve both problems in time O(n/sup 2/3/log/sup 4/3/) per combinatorial change in the tree (or randomized O(n/sup 2/3/log/sup 4/3/ n) per change). Our time bounds reduce to O(n/sup 1/2/log/sup 3/2/ n) per change (O(n/sup 1/2/log n) randomized) for planar graphs or other minor-closed families of graphs, and O(n/sup 1/4/log/sup 3/2/ n) per change (O(n/sup 1/4/ log n) randomized) for planar graphs with weight changes but no insertions or deletions.

Details

FOCS Conference 1997 Conference Paper

Approximating Shortest Paths on an Nonconvex Polyhedron

  • Kasturi R. Varadarajan
  • Pankaj K. Agarwal

We present an approximation algorithm that, given the boundary P of a simple, nonconvex polyhedron in R/sup 3/, and two points s and t on P, constructs a path on P between s and t whose length is at most 7(1+/spl epsi/)d/sub P/(s, t), where d/sub P/(s, t) is the length of the shortest path between s and t on P, and /spl epsi/>0 is an arbitrarily small positive constant. The algorithm runs in O(n/sup 5/3/ log/sup 5/3/ n) time, where n is the number of vertices in P. We also present a slightly faster algorithm that runs in O(n/sup 8/5/ log/sup 8/5/ n) time and returns a path whose length is at most 15(1+/spl epsi/)d/sub P/(s, t).

Details

ICRA Conference 1997 Conference Paper

Nonholonomic path planning for pushing a disk among obstacles

  • Pankaj K. Agarwal
  • Jean-Claude Latombe
  • Rajeev Motwani 0001
  • Prabhakar Raghavan

We consider the path-planning problem for a robot pushing an object in an environment containing obstacles. This new variant of the classical robot path-planning problem has several interesting geometric aspects, which we explore. We focus on the setting where the robot makes a point contact with the object which is assumed to be a unit disk, while the obstacles are assumed to be polygonal.

Details

FOCS Conference 1996 Conference Paper

Binary Search Partitions for Fat Rectangles

  • Pankaj K. Agarwal
  • Edward F. Grove
  • T. M. Murali 0001
  • Jeffrey Scott Vitter

The authors consider the practical problem of constructing binary space partitions (BSPs) for a set S of n orthogonal, nonintersecting, two-dimensional rectangles in R/sup 3/ such that the aspect ratio of each rectangle in S is at most /spl alpha/, for some constant a /spl alpha//spl ges/1. They present an n2/sup O(/spl radic/logn)/-time algorithm to build a binary space partition of size n2/sup O(/spl radic/logn)/ for S. They also show that if m of the n rectangles in S have aspect ratios greater than /spl alpha/, they can contact a BSP of size n/spl radic/m2/sup O(/spl radic/logn)/ for S in n/spl radic/2/sup O(/spl radic/logn)/ time. The constants of proportionality in the big-oh terms are linear in log /spl alpha/. They extend these results to cases in which the input contains non-orthogonal or intersecting objects.

Details

FOCS Conference 1992 Conference Paper

Dynamic Half-Space Reporting, Geometric Optimization, and Minimum Spanning Trees

  • Pankaj K. Agarwal
  • David Eppstein
  • Jirí Matousek 0001

The authors describe dynamic data structures for half-space range reporting and for maintaining the minima of a decomposable function. Using these data structures, they obtain efficient dynamic algorithms for a number of geometric problems, including closest/farthest neighbor searching, fixed dimension linear programming, bi-chromatic closest pair, diameter, and Euclidean minimum spanning tree. >

Details

MFCS Conference 1992 Invited Paper

On Range Searching with Semialgebraic Sets

  • Pankaj K. Agarwal
  • Jirí Matousek 0001

Abstract Let P be a set of n points in ℝ d ( d a small fixed positive integer), and let Γ be a collection of subsets of ℝ d, each of which is defined by a constant number of bounded degree polynomials. The Γ-range searching problem is defined as: Preprocess P into a data structure, so that all points of P lying in a given γ Γ can be counted (or reported) efficiently. Generalizing the simplex range searching techniques, we construct a data structure for Γ-range searching with nearly linear space and preprocessing time, which can answer a query in time O(n 1−1/ b+δ ), where d≤b≤ 2 d −3 and δ> 0 is an arbitrarily small constant. The actual value of b is related to the problem of partitioning arrangements of algebraic surfaces into constant-complexity cells.

Details
v2026.09.13