Source author record

Pankaj K. Agarwal

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms math.MG Networking and Internet Architecture Robotics

Catalog footprint

Research overview

18works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Deterministic, Near-Linear $\varepsilon$ -Approximation Algorithm for Geometric Bipartite Matching

Given point sets $A$ and $B$ in $\mathbb{R}^d$ where $A$ and $B$ have equal size $n$ for some constant dimension $d$ and a parameter $\varepsilon>0$ , we present the first deterministic algorithm that computes, in $n\cdot(\varepsilon^{-1} \log n)^{O(d)}$ time, a perfect matching between $A$ and $B$ whose cost is within a $(1+\varepsilon)$ factor of the optimal under any $\smash{\ell_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 $\varepsilon$ -approximation algorithm takes $Ω(n^{3/2})$ time. Our algorithm constructs a (refinement of a) tree cover of $\mathbb{R}^d$ , and we develop several new tools to apply a tree-cover based approach to compute an $\varepsilon$ -approximate perfect matching.

preprint2021arXiv

An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications

In 2015, Guth proved that if $S$ is a collection of $n$ $g$ -dimensional semi-algebraic sets in $\mathbb{R}^d$ and if $D\geq 1$ is an integer, then there is a $d$ -variate polynomial $P$ of degree at most $D$ so that each connected component of $\mathbb{R}^d\setminus Z(P)$ intersects $O(n/D^{d-g})$ sets from $S$ . Such a polynomial is called a generalized partitioning polynomial. We present a randomized algorithm that computes such polynomials efficiently -- the expected running time of our algorithm is linear in $|S|$ . Our approach exploits the technique of quantifier elimination combined with that of $ε$ -samples. We also present an extension of our construction to multi-level polynomial partitioning for semi-algebraic sets in $\mathbb{R}^d$ . We present five applications of our result. The first is a data structure for answering point-enclosure queries among a family of semi-algebraic sets in $\mathbb{R}^d$ in $O(\log n)$ time, with storage complexity and expected preprocessing time of $O(n^{d+ε})$ . The second is a data structure for answering range-searching queries with semi-algebraic ranges in $\mathbb{R}^d$ in $O(\log n)$ time, with $O(n^{t+ε})$ storage and expected preprocessing time, where $t > 0$ is an integer that depends on $d$ and the description complexity of the ranges. The third is a data structure for answering vertical ray-shooting queries among semi-algebraic sets in $\mathbb{R}^{d}$ in $O(\log^2 n)$ time, with $O(n^{d+ε})$ storage and expected preprocessing time. The fourth is an efficient algorithm for cutting algebraic curves in $\mathbb{R}^2$ into pseudo-segments. The fifth application is for eliminating depth cycles among triangles in $\mathbb{R}^3$ , where we show a nearly-optimal algorithm to cut $n$ pairwise disjoint non-vertical triangles in $\mathbb{R}^3$ into pieces that form a depth order.

preprint2020arXiv

1D and 2D Flow Routing on a Terrain

An important problem in terrain analysis is modeling how water flows across a terrain creating floods by forming channels and filling depressions. In this paper we study a number of \emph{flow-query} related problems: Given a terrain $Σ$ , represented as a triangulated $xy$ -monotone surface with $n$ vertices, a rain distribution $R$ which may vary over time, determine how much water is flowing over a given edge as a function of time. We develop internal-memory as well as I/O-efficient algorithms for flow queries. This paper contains four main results: (i) We present an internal-memory algorithm that preprocesses $Σ$ into a linear-size data structure that for a (possibly time varying) rain distribution $R$ can return the flow-rate functions of all edges of $Σ$ in $O(ρk+|ϕ| \log n)$ time, where $ρ$ is the number of sinks in $Σ$ , $k$ is the number of times the rain distribution changes, and $|ϕ|$ is the total complexity of the flow-rate functions that have non-zero values; (ii) We also present an I/O-efficient algorithm for preprocessing $Σ$ into a linear-size data structure so that for a rain distribution $R$ , it can compute the flow-rate function of all edges using $O(\text{Sort}(|ϕ|))$ I/Os and $O(|ϕ| \log |ϕ|)$ internal computation time. (iii) $Σ$ can be preprocessed into a linear-size data structure so that for a given rain distribution $R$ , the flow-rate function of an edge $(q,r) \in Σ$ under the single-flow direction (SFD) model can be computed more efficiently. (iv) We present an algorithm for computing the two-dimensional channel along which water flows using Manning's equation; a widely used empirical equation that relates the flow-rate of water in an open channel to the geometry of the channel along with the height of water in the channel.

preprint2020arXiv

Dynamic geometric set cover and hitting set

We investigate dynamic versions of geometric set cover and hitting set where points and ranges may be inserted or deleted, and we want to efficiently maintain an (approximately) optimal solution for the current problem instance. While their static versions have been extensively studied in the past, surprisingly little is known about dynamic geometric set cover and hitting set. For instance, even for the most basic case of one-dimensional interval set cover and hitting set, no nontrivial results were known. The main contribution of our paper are two frameworks that lead to efficient data structures for dynamically maintaining set covers and hitting sets in $\mathbb{R}^1$ and $\mathbb{R}^2$ . The first framework uses bootstrapping and gives a $(1+\varepsilon)$ -approximate data structure for dynamic interval set cover in $\mathbb{R}^1$ with $O(n^α/\varepsilon)$ amortized update time for any constant $α> 0$ ; in $\mathbb{R}^2$ , this method gives $O(1)$ -approximate data structures for unit-square (and quadrant) set cover and hitting set with $O(n^{1/2+α})$ amortized update time. The second framework uses local modification, and leads to a $(1+\varepsilon)$ -approximate data structure for dynamic interval hitting set in $\mathbb{R}^1$ with $\widetilde{O}(1/\varepsilon)$ amortized update time; in $\mathbb{R}^2$ , it gives $O(1)$ -approximate data structures for unit-square (and quadrant) set cover and hitting set in the \textit{partially} dynamic settings with $\widetilde{O}(1)$ amortized update time.

preprint2016arXiv

Approximating Dynamic Time Warping and Edit Distance for a Pair of Point Sequences

We give the first subquadratic-time approximation schemes for dynamic time warping (DTW) and edit distance (ED) of several natural families of point sequences in $\mathbb{R}^d$ , for any fixed $d \ge 1$ . In particular, our algorithms compute $(1+\varepsilon)$ -approximations of DTW and ED in time near-linear for point sequences drawn from k-packed or k-bounded curves, and subquadratic for backbone sequences. Roughly speaking, a curve is $κ$ -packed if the length of its intersection with any ball of radius $r$ is at most $κ\cdot r$ , and a curve is $κ$ -bounded if the sub-curve between two curve points does not go too far from the two points compared to the distance between the two points. In backbone sequences, consecutive points are spaced at approximately equal distances apart, and no two points lie very close together. Recent results suggest that a subquadratic algorithm for DTW or ED is unlikely for an arbitrary pair of point sequences even for $d=1$ . Our algorithms work by constructing a small set of rectangular regions that cover the entries of the dynamic programming table commonly used for these distance measures. The weights of entries inside each rectangle are roughly the same, so we are able to use efficient procedures to approximately compute the cheapest paths through these rectangles.

preprint2016arXiv

Nearest-Neighbor Searching Under Uncertainty II

Nearest-neighbor search, which returns the nearest neighbor of a query point in a set of points, is an important and widely studied problem in many fields, and it has wide range of applications. In many of them, such as sensor databases, location-based services, face recognition, and mobile data, the location of data is imprecise. We therefore study nearest-neighbor queries in a probabilistic framework in which the location of each input point is specified as a probability distribution function. We present efficient algorithms for - computing all points that are nearest neighbors of a query point with nonzero probability; and - estimating the probability of a point being the nearest neighbor of a query point, either exactly or within a specified additive error.

preprint2015arXiv

Stable Delaunay Graphs

Let $P$ be a set of $n$ points in $\mathrm{R}^2$ , and let $\mathrm{DT}(P)$ denote its Euclidean Delaunay triangulation. We introduce the notion of an edge of $\mathrm{DT}(P)$ being {\it stable}. Defined in terms of a parameter $α>0$ , a Delaunay edge $pq$ is called $α$ -stable, if the (equal) angles at which $p$ and $q$ see the corresponding Voronoi edge $e_{pq}$ are at least $α$ . A subgraph $G$ of $\mathrm{DT}(P)$ is called {\it $(cα, α)$ -stable Delaunay graph} ( $\mathrm{SDG}$ in short), for some constant $c \ge 1$ , if every edge in $G$ is $α$ -stable and every $cα$ -stable of $\mathrm{DT}(P)$ is in $G$ . We show that if an edge is stable in the Euclidean Delaunay triangulation of $P$ , then it is also a stable edge, though for a different value of $α$ , in the Delaunay triangulation of $P$ under any convex distance function that is sufficiently close to the Euclidean norm, and vice-versa. In particular, a $6α$ -stable edge in $\mathrm{DT}(P)$ is $α$ -stable in the Delaunay triangulation under the distance function induced by a regular $k$ -gon for $k \ge 2π/α$ , and vice-versa. Exploiting this relationship and the analysis in~\cite{polydel}, we present a linear-size kinetic data structure (KDS) for maintaining an $(8α,α)$ - $\mathrm{SDG}$ as the points of $P$ move. If the points move along algebraic trajectories of bounded degree, the KDS processes nearly quadratic events during the motion, each of which can processed in $O(\log n)$ time. Finally, we show that a number of useful properties of $\mathrm{DT}(P)$ are retained by $\mathrm{SDG}$ of $P$ .

preprint2014arXiv

Convex Hulls under Uncertainty

We study the convex-hull problem in a probabilistic setting, motivated by the need to handle data uncertainty inherent in many applications, including sensor databases, location-based services and computer vision. In our framework, the uncertainty of each input site is described by a probability distribution over a finite number of possible locations including a \emph{null} location to account for non-existence of the point. Our results include both exact and approximation algorithms for computing the probability of a query point lying inside the convex hull of the input, time-space tradeoffs for the membership queries, a connection between Tukey depth and membership queries, as well as a new notion of $\some$-hull that may be a useful representation of uncertain hulls.

preprint2014arXiv

Kinetic Voronoi Diagrams and Delaunay Triangulations under Polygonal Distance Functions

Let $P$ be a set of $n$ points and $Q$ a convex $k$ -gon in ${\mathbb R}^2$ . We analyze in detail the topological (or discrete) changes in the structure of the Voronoi diagram and the Delaunay triangulation of $P$ , under the convex distance function defined by $Q$ , as the points of $P$ move along prespecified continuous trajectories. Assuming that each point of $P$ moves along an algebraic trajectory of bounded degree, we establish an upper bound of $O(k^4nλ_r(n))$ on the number of topological changes experienced by the diagrams throughout the motion; here $λ_r(n)$ is the maximum length of an $(n,r)$ -Davenport-Schinzel sequence, and $r$ is a constant depending on the algebraic degree of the motion of the points. Finally, we describe an algorithm for efficiently maintaining the above structures, using the kinetic data structure (KDS) framework.

preprint2014arXiv

Maintaining Contour Trees of Dynamic Terrains

We consider maintaining the contour tree $\mathbb{T}$ of a piecewise-linear triangulation $\mathbb{M}$ that is the graph of a time varying height function $h: \mathbb{R}^2 \rightarrow \mathbb{R}$ . We carefully describe the combinatorial change in $\mathbb{T}$ that happen as $h$ varies over time and how these changes relate to topological changes in $\mathbb{M}$ . We present a kinetic data structure that maintains the contour tree of $h$ over time. Our data structure maintains certificates that fail only when $h(v)=h(u)$ for two adjacent vertices $v$ and $u$ in $\mathbb{M}$ , or when two saddle vertices lie on the same contour of $\mathbb{M}$ . A certificate failure is handled in $O(\log(n))$ time. We also show how our data structure can be extended to handle a set of general update operations on $\mathbb{M}$ and how it can be applied to maintain topological persistence pairs of time varying functions.

preprint2013arXiv

Computing Similarity between a Pair of Trajectories

With recent advances in sensing and tracking technology, trajectory data is becoming increasingly pervasive and analysis of trajectory data is becoming exceedingly important. A fundamental problem in analyzing trajectory data is that of identifying common patterns between pairs or among groups of trajectories. In this paper, we consider the problem of identifying similar portions between a pair of trajectories, each observed as a sequence of points sampled from it. We present new measures of trajectory similarity --- both local and global --- between a pair of trajectories to distinguish between similar and dissimilar portions. Our model is robust under noise and outliers, it does not make any assumptions on the sampling rates on either trajectory, and it works even if they are partially observed. Additionally, the model also yields a scalar similarity score which can be used to rank multiple pairs of trajectories according to similarity, e.g. in clustering applications. We also present efficient algorithms for computing the similarity under our measures; the worst-case running time is quadratic in the number of sample points. Finally, we present an extensive experimental study evaluating the effectiveness of our approach on real datasets, comparing with it with earlier approaches, and illustrating many issues that arise in trajectory data. Our experiments show that our approach is highly accurate in distinguishing similar and dissimilar portions as compared to earlier methods even with sparse sampling.

preprint2013arXiv

On Range Searching with Semialgebraic Sets II

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 semialgebraic 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 < r \le n$ , there exists a $d$ -variate polynomial $f$ of degree $O(r^{1/d})$ such that each connected component of $\R^d\setminus Z(f)$ contains at most $n/r$ points of $P$ , where $Z(f)$ is the zero set of $f$ . We present an efficient randomized algorithm for computing such a polynomial partition, which is of independent interest and is likely to have additional applications.

preprint2012arXiv

Computing the Discrete Fréchet Distance in Subquadratic Time

The Fréchet distance is a similarity measure between two curves $A$ and $B$ : Informally, it is the minimum length of a leash required to connect a dog, constrained to be on $A$ , and its owner, constrained to be on $B$ , as they walk without backtracking along their respective curves from one endpoint to the other. The advantage of this measure on other measures such as the Hausdorff distance is that it takes into account the ordering of the points along the curves. 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 pebbles on the curves $A$ and $B$ , respectively. These frogs hop from a pebble to the next without backtracking. The discrete Fréchet distance can be computed by a rather straightforward quadratic dynamic programming algorithm. However, despite a considerable amount of work on this problem and its variations, there is no subquadratic algorithm known, even for approximation versions of the problem. In this paper we present a subquadratic algorithm for computing the discrete Fréchet distance between two sequences of points in the plane, of respective lengths $m\le n$ . The algorithm runs in $O(\dfrac{mn\log\log n}{\log n})$ time and uses $O(n+m)$ 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 automata.

preprint2012arXiv

Sparsification of Motion-Planning Roadmaps by Edge Contraction

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%.

preprint2011arXiv

Kinetic Stable Delaunay Graphs

We consider the problem of maintaining the Euclidean Delaunay triangulation $\DT$ of a set $P$ of $n$ moving points in the plane, along algebraic trajectories of constant description complexity. Since the best known upper bound on the number of topological changes in the full $\DT$ is nearly cubic, we seek to maintain a suitable portion of it that is less volatile yet retains many useful properties. We introduce the notion of a stable Delaunay graph, which is a dynamic subgraph of the Delaunay triangulation. The stable Delaunay graph (a) is easy to define, (b) experiences only a nearly quadratic number of discrete changes, (c) is robust under small changes of the norm, and (d) possesses certain useful properties. The stable Delaunay graph ($\SDG$ in short) is defined in terms of a parameter $α>0$ , and consists of Delaunay edges $pq$ for which the angles at which $p$ and $q$ see their Voronoi edge $e_{pq}$ are at least $α$ . We show that (i) $\SDG$ always contains at least roughly one third of the Delaunay edges; (ii) it contains the $β$ -skeleton of $P$ , for $β=1+Ω(α^2)$ ; (iii) it is stable, in the sense that its edges survive for long periods of time, as long as the orientations of the segments connecting (nearby) points of $P$ do not change by much; and (iv) stable Delaunay edges remain stable (with an appropriate redefinition of stability) if we replace the Euclidean norm by any sufficiently close norm. In particular, we can approximate the Euclidean norm by a polygonal norm (namely, a regular $k$ -gon, with $k=Θ(1/α)$ ), and keep track of a Euclidean $\SDG$ by maintaining the full Delaunay triangulation of $P$ under the polygonal norm. We describe two kinetic data structures for maintaining $\SDG$. Both structures use $O^*(n)$ storage and process $O^*(n^2)$ events during the motion, each in $O^*(1)$ time.

preprint2010arXiv

On Channel-Discontinuity-Constraint Routing in Wireless Networks

Multi-channel wireless networks are increasingly being employed as infrastructure networks, e.g. in metro areas. Nodes in these networks frequently employ directional antennas to improve spatial throughput. In such networks, given a source and destination, it is of interest to compute an optimal path and channel assignment on every link in the path such that the path bandwidth is the same as that of the link bandwidth and such a path satisfies the constraint that no two consecutive links on the path are assigned the same channel, referred to as "Channel Discontinuity Constraint" (CDC). CDC-paths are also quite useful for TDMA system, where preferably every consecutive links along a path are assigned different time slots. This paper contains several contributions. We first present an $O(N^{2})$ distributed algorithm for discovering the shortest CDC-path between given source and destination. This improves the running time of the $O(N^{3})$ centralized algorithm of Ahuja et al. for finding the minimum-weight CDC-path. Our second result is a generalized $t$ -spanner for CDC-path; For any $θ>0$ we show how to construct a sub-network containing only $O(\frac{N}θ)$ edges, such that that length of shortest CDC-paths between arbitrary sources and destinations increases by only a factor of at most $(1-2\sin{\tfracθ{2}})^{-2}$ . We propose a novel algorithm to compute the spanner in a distributed manner using only $O(n\log{n})$ messages. An important conclusion of this scheme is in the case of directional antennas are used. In this case, it is enough to consider only the two closest nodes in each cone.

preprint2010arXiv

Stability of epsilon-Kernels

Given a set P of n points in |R^d, an eps-kernel K subset P approximates the directional width of P in every direction within a relative (1-eps) factor. In this paper we study the stability of eps-kernels under dynamic insertion and deletion of points to P and by changing the approximation factor eps. In the first case, we say an algorithm for dynamically maintaining a eps-kernel is stable if at most O(1) points change in K as one point is inserted or deleted from P. We describe an algorithm to maintain an eps-kernel of size O(1/eps^{(d-1)/2}) in O(1/eps^{(d-1)/2} + log n) time per update. Not only does our algorithm maintain a stable eps-kernel, its update time is faster than any known algorithm that maintains an eps-kernel of size O(1/eps^{(d-1)/2}). Next, we show that if there is an eps-kernel of P of size k, which may be dramatically less than O(1/eps^{(d-1)/2}), then there is an (eps/2)-kernel of P of size O(min {1/eps^{(d-1)/2}, k^{floor(d/2)} log^{d-2} (1/eps)}). Moreover, there exists a point set P in |R^d and a parameter eps > 0 such that if every eps-kernel of P has size at least k, then any (eps/2)-kernel of P has size Omega(k^{floor(d/2)}).

preprint2010arXiv

The 2-Center Problem in Three Dimensions

Let P be a set of n points in R^3. The 2-center problem for P is to find two congruent balls of minimum radius whose union covers P. We present two randomized algorithms for computing a 2-center of P. The first algorithm runs in O(n^3 log^5 n) expected time, and the second algorithm runs in O((n^2 log^5 n) /(1-r*/r_0)^3) expected time, where r* is the radius of the 2-center balls of P and r_0 is the radius of the smallest enclosing ball of P. The second algorithm is faster than the first one as long as r* is not too close to r_0, which is equivalent to the condition that the centers of the two covering balls be not too close to each other.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Pankaj K. Agarwal

Research overview

Is this your work?

18 publications

Deterministic, Near-Linear $\varepsilon$ -Approximation Algorithm for Geometric Bipartite Matching

An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications

1D and 2D Flow Routing on a Terrain

Dynamic geometric set cover and hitting set

Approximating Dynamic Time Warping and Edit Distance for a Pair of Point Sequences

Nearest-Neighbor Searching Under Uncertainty II

Stable Delaunay Graphs

Convex Hulls under Uncertainty

Kinetic Voronoi Diagrams and Delaunay Triangulations under Polygonal Distance Functions

Maintaining Contour Trees of Dynamic Terrains

Computing Similarity between a Pair of Trajectories

On Range Searching with Semialgebraic Sets II

Computing the Discrete Fréchet Distance in Subquadratic Time

Sparsification of Motion-Planning Roadmaps by Edge Contraction

Kinetic Stable Delaunay Graphs

On Channel-Discontinuity-Constraint Routing in Wireless Networks

Stability of epsilon-Kernels

The 2-Center Problem in Three Dimensions

See the researcher in context

Building this map preview

Pankaj K. Agarwal

Research overview

Is this your work?

18 publications

Deterministic, Near-Linear ε\varepsilonε-Approximation Algorithm for Geometric Bipartite Matching

An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications

1D and 2D Flow Routing on a Terrain

Dynamic geometric set cover and hitting set

Approximating Dynamic Time Warping and Edit Distance for a Pair of Point Sequences

Nearest-Neighbor Searching Under Uncertainty II

Stable Delaunay Graphs

Convex Hulls under Uncertainty

Kinetic Voronoi Diagrams and Delaunay Triangulations under Polygonal Distance Functions

Maintaining Contour Trees of Dynamic Terrains

Computing Similarity between a Pair of Trajectories

On Range Searching with Semialgebraic Sets II

Computing the Discrete Fréchet Distance in Subquadratic Time

Sparsification of Motion-Planning Roadmaps by Edge Contraction

Kinetic Stable Delaunay Graphs

On Channel-Discontinuity-Constraint Routing in Wireless Networks

Stability of epsilon-Kernels

The 2-Center Problem in Three Dimensions

See the researcher in context

Building this map preview

Deterministic, Near-Linear $\varepsilon$ -Approximation Algorithm for Geometric Bipartite Matching