Scholars@Duke
Pankaj K. Agarwal

Pankaj K. Agarwal

RJR Nabisco Distinguished Professor of Computer Science in Trinity College of Arts and Sciences
Computer Science
pankaj@cs.duke.edu
Box 90129, Durham, NC 27708-0129
D214A Lev Sci Res Ctr, Durham, NC 27708

Selected Publications

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

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

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