Pankaj K. Agarwal

Conference Leibniz International Proceedings in Informatics, LIPIcs · June 1, 2024 Let P be a set of m points in R2, let Σ be a set of n semi-algebraic sets of constant complexity in R2, let (S, +) be a semigroup, and let w : P → S be a weight function on the points of P. We describe a randomized algorithm for computing w(P ∩ σ) for ever ... Full text Cite

Computing Data Distribution from Query Selectivities

Conference Leibniz International Proceedings in Informatics, LIPIcs · March 1, 2024 We are given a set Z = {(R1, s1), ..., (Rn, sn)}, where each Ri is a range in Rd, such as rectangle or ball, and si ∈ [0, 1] denotes its selectivity. The goal is to compute a small-size discrete data distribution D = {(q1, w1), ..., (qm, wm)}, where qj ∈ R ... Full text Cite

On reverse shortest paths in geometric proximity graphs

Journal Article Computational Geometry: Theory and Applications · February 1, 2024 Let S be a set of n geometric objects of constant complexity (e.g., points, line segments, disks, ellipses) in R2, and let ϱ:S×S→R≥0 be a distance function on S. For a parameter r≥0, we define the proximity graph G(r)=(S,E) where E={(e1,e2)∈S×S|e1≠e2,ϱ(e1, ... Full text Cite

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

Conference Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms · January 1, 2024 Vertical decomposition is a widely used general technique for decomposing the cells of arrangements of semi-algebraic sets in Rd into constant-complexity subcells. In this paper, we settle in the affirmative a few long-standing open problems involving the ... Full text Cite

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

Conference Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms · January 1, 2024 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 ... Full text Cite

Near-Optimal Min-Sum Motion Planning for Two Square Robots in a Polygonal Environment

Conference Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms · January 1, 2024 Let W ⊂ R2 be a planar polygonal environment (i.e., a polygon potentially with holes) with a total of n vertices, and let A, B be two robots, each modeled as an axis-aligned unit square, that can translate inside W. Given source and target placements sA, t ... Full text Cite

Fast Approximation Algorithms for Piercing Boxes by Points

Conference Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms · January 1, 2024 Let B = {b1, ..., bn} be a set of n axis-aligned boxes in Rd where d ≥ 2 is a constant. The piercing problem is to compute a smallest set of points N ⊂ Rd that hits every box in B, i.e., N ∩bi ≠ ∅, for i = 1, ..., n. The problem is known to be NP-Hard. Let ... Full text Cite

Computing Instance-Optimal Kernels in Two Dimensions

Journal Article Discrete and Computational Geometry · January 1, 2024 Let P be a set of n points in R2. For a parameter ε∈(0,1), a subset C⊆P is an ε-kernel of P if the projection of the convex hull of C approximates that of P within (1-ε)-factor in every direction. The set C is a weakε-kernel of P if its directional width a ... Full text Cite

Multi-robot motion planning for unit discs with revolving areas

Journal Article Computational Geometry: Theory and Applications · October 1, 2023 We study the problem of motion planning for a collection of n labeled unit disc robots in a polygonal environment. We assume that the robots have revolving areas around their start and final positions: that each start and each final is contained in a radiu ... Full text Cite

Computing Instance-Optimal Kernels in Two Dimensions

Conference Leibniz International Proceedings in Informatics, LIPIcs · June 1, 2023 Let P be a set of n points in R2. For a parameter (Equation presented), a subset C Ď P is an ε-kernel of P if the projection of the convex hull of C approximates that of P within (Equation presented)-factor in every direction. The set C is a weak ε-kernel ... Full text Cite

Line Intersection Searching Amid Unit Balls in 3-Space

Conference Leibniz International Proceedings in Informatics, LIPIcs · June 1, 2023 Let B be a set of n unit balls in R3. We present a linear-size data structure for storing B that can determine in (Equation presented) time whether a query line intersects any ball of B and report all k such balls in additional O(k) time. The data structur ... Full text Cite

A HIGHER PRECISION ALGORITHM FOR COMPUTING THE 1-WASSERSTEIN DISTANCE

Conference 11th International Conference on Learning Representations, ICLR 2023 · January 1, 2023 We consider the problem of computing the 1-Wasserstein distance W(µ, ν) between two d-dimensional discrete distributions µ and ν whose support lie within the unit hypercube. There are several algorithms that estimate W(µ, ν) within an additive error of ε. ... Cite

Maintaining the Union of Unit Discs under Insertions with Near-Optimal Overhead

Journal Article ACM Transactions on Algorithms · October 11, 2022 We present efficient dynamic data structures for maintaining the union of unit discs and the lower envelope of pseudo-lines in the plane. More precisely, we present three main results in this paper: (i)We present a linear-size data structure to maintain th ... Full text Cite

Dynamic Geometric Set Cover and Hitting Set

Conference ACM Transactions on Algorithms · October 10, 2022 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 ... Full text Cite

All Politics is Local: Redistricting via Local Fairness

Conference Advances in Neural Information Processing Systems · January 1, 2022 In this paper, we propose to use the concept of local fairness for auditing and ranking redistricting plans. Given a redistricting plan, a deviating group is a population-balanced contiguous region in which a majority of individuals are of the same interes ... Cite

Compact encoding strategies for DNA sequence similarity search.

Conference Proceedings. International Conference on Intelligent Systems for Molecular Biology · January 1996 Determining whether two DNA sequences are similar is an essential component of DNA sequence analysis. Dynamic programming is the algorithm of choice if computational time is not the most important consideration. Heuristic search tools, such as BLAST, are c ... Cite

The Repeat Pattern Toolkit (RPT): analyzing the structure and evolution of the C. elegans genome.

Conference Proceedings. International Conference on Intelligent Systems for Molecular Biology · January 1994 Over 3.6 million bases of DNA sequence from chromosome III of the C. elegans have been determined. The availability of this extended region of contiguous sequence has allowed us to analyze the nature and prevalence of repetitive sequences in the genome of ... Cite