About

Pankaj K. Agarwal is the RJR Nabisco Distinguished Professor of Computer Science in Trinity College of Arts and Sciences at Duke University. His academic appointments include being a Professor of Computer Science since 1998 and a Professor of Mathematics since 2009 within the same college. He has held the Bass Fellowship since 2005. His research focuses on geometric algorithms, discrete geometry, geometric data analysis, data structures, database systems, data mining, robotics algorithms, and geographic information systems. Agarwal has made significant contributions to these fields through his research, publications, and professional activities, establishing himself as a leading figure in computational geometry and related areas.

Research topics

• Computer Science
• Mathematics
• Algorithm
• Data Mining
• Artificial Intelligence
• Information Retrieval
• Machine Learning
• Geometry
• Statistics
• Mathematical optimization
• Combinatorics
• Real-time computing
• World Wide Web

Selected publications

• Near-Optimal Min-Sum Multi-Robot Motion Planning in a Planar Polygonal Environment

  Society for Industrial and Applied Mathematics eBooks · 2026-01-01

  book-chapter1st authorCorresponding

  Let \(\mathscr{W} \subset \mathbb{R}^2\) be a planar polygonal environment with n vertices, and let \([k] = \{1, \ldots, k\}\) denote \(k\) unit-square robots translating in \(\mathscr{W}\). Given source and target placements \(s_1, t_1, \ldots, s_k, t_k, \in \mathscr{W}\) for each robot, we wish to compute a collision-free motion plan \(\boldsymbol \pi\), i.e., a coordinated motion for each robot \(i\) along a continuous path from \(s_i\) to \(t_i\), so that robot \(i\) does not leave \(\mathscr{W}\) or collide with any other robot \(j\). Moreover, we additionally require that \(\boldsymbol \pi\) minimizes the sum of the path lengths; this variant is known as min-sum motion planning.

  PublisherDOI

• Computing the Heaviest Disk and Related Problems

  Society for Industrial and Applied Mathematics eBooks · 2026-01-01

  book-chapter1st authorCorresponding

  We present an algorithm that, given \(m\) points and \(n\) disks in \(\mathbb{R}^2\), computes the disk that contains the maximum number of points. The algorithm runs in \(O^*(m^{2/3} n^{2/3} + m^{32/59} n^{145/177} + m + n)\) expected time, where the \(O^*(\cdot)\) notation hides factors of the form \(n^\varepsilon\), for an arbitrarily small \(\varepsilon \gt 0\), and coefficients that depend on \(\varepsilon\). The algorithm is faster than existing algorithms for \(m \lt n^{5/4}\), and it has similar performance bounds for \(m \ge n^{5/4}\). As a matter of fact, except for disks that are fully contained in other disks, the algorithm counts the number of input points in each disk.

  PublisherDOI

• A Subquadratic Algorithm for Computing the L₁-Distance Between Two Terrains

  DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2025-01-01

  preprintOpen access1st authorCorresponding

  We study the problem of computing the L₁-distance between two piecewise-linear bivariate functions f and g, defined over a bounded polygonal domain 𝕄 ⊂ ℝ², that is, computing the quantity ‖f-g‖₁ = ∫_𝕄 |f(x,y)-g(x,y)| dx dy. If f and g are defined by linear interpolation over triangulations 𝐓_f and 𝐓_g, respectively, of 𝕄 with a total of n triangles, we show that ‖f-g‖₁ can be computed in Õ(n^α) time, where α = max{(ω+1)/2, 8/5}, ω is the matrix multiplication exponent, and Õ notation hides factors of the form n^ε for any ε > 0. This bound holds for the currently best known value of ω, which is approximately 2.37. More generally, if the complexity of the overlay of 𝐓_f and 𝐓_g is κ, then the runtime of our algorithm is Õ(κ^{α-1}n^{2-α}).

  PublisherOA PDFDOI

• Semi-Algebraic Off-line Range Searching and Biclique Partitions in the Plane

  Discrete & Computational Geometry · 2025-10-21

  article1st authorCorresponding
  PublisherDOI

• Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems

  ACM Transactions on Algorithms · 2025-03-11

  articleOpen access1st authorCorresponding

  Let \(\mathcal{T}\) be a set of \(n\) flat (planar) semi-algebraic regions in \(\mathbb{R}^{3}\) of constant complexity (e.g., triangles, disks), which we call plates . We wish to preprocess \(\mathcal{T}\) into a data structure so that for a query object \(\gamma\) , which is also a plate, we can quickly answer various intersection queries , such as detecting whether \(\gamma\) intersects any plate of \(\mathcal{T}\) , reporting all the plates intersected by \(\gamma\) , or counting them. We also consider two simpler cases of this general setting: (i) the input objects are plates and the query objects are constant-degree parametrized algebraic arcs in \(\mathbb{R}^{3}\) ( arcs , for short), or (ii) the input objects are arcs and the query objects are plates in \(\mathbb{R}^{3}\) . Besides being interesting in their own right, the data structures for these two special cases form the building blocks for handling the general case. By combining the polynomial-partitioning technique with additional tools from real algebraic geometry, we present many different data structures for intersection queries, which also provide trade-offs between their size and query time. For example, if \(\mathcal{T}\) is a set of plates and the query objects are algebraic arcs, we obtain a data structure that uses \(O^{*}(n^{4/3})\) storage (where the \(O^{*}(\cdot)\) notation hides factors of the form \(n^{\varepsilon}\) , for an arbitrarily small \(\varepsilon>0\) ) and answers an arc-intersection query in \(O^{*}(n^{2/3})\) time. This result is significant since the exponents do not depend on the specific shape of the input and query objects. We generalize and slightly improve this result: for a parameter \(s\in[n^{4/3},n^{t_{q}}]\) , where \({t_{q}}\geq 3\) is the number of real parameters needed to specify a query arc, the query time can be decreased to \(O^{*}((n/s^{1/{t_{q}}})^{\tfrac{2/3}{1-1/{t_{q}}}})\) by increasing the storage to \(O^{*}(s)\) . Our approach can be extended to many additional intersection-searching problems in three dimensions, even when the input or query objects are not flat.

  PublisherDOI

• Adversarial Learning for Graph-Based Deep Models with a Focus on Crafting Effective Perturbations Against GNNs

  2025-11-28

  article

  Using Graph Neural Networks (GNNs) more often in social networks, recommendation systems and bioinformatics has made it clear that such networks are prone to adversarial attacks. Such vulnerabilities can create major problems such as incorrect information circulating or the breakdown of predictive systems. This research proposes an innovative way to attack GNNs by using both K-Means clustering and Class Activation Mapping (CAM). In contrast to FGSM, IFGSM and Carlini-Wagner (CW) techniques, the approach presented here creates perturbations that are more difficult to notice, while continuing to be highly effective in generating attacks. The methodology transforms each MNIST image into a graph node and uses the pixel patterns to guide how the graph is made. The system reaches great misclassification rates, even though the range of visible defects is minimal. Performance evaluation reveals that the method proposed here lowers classifier accuracy and is more effective when an attack is designed to exploit specific security vulnerabilities in comparison to other approaches. The fact that SVMs can handle more data than Logistic Regression models verifies that how a classifier is built has a strong effect on its vulnerabilities. It provides a useful approach to assessing and improving resistance in GNNs, making a difference in adversarial machine learning and helping to build better defenses in practical uses. The suggested K-Means clustering and CAM approach reliably achieves an overall accuracy of up to 97.5% when applied to various datasets and classifiers.

  PublisherDOI

• PAR2QO: Parametric Penalty-Aware Robust Query Optimization

  Proceedings of the VLDB Endowment · 2025-07-01 · 1 citations

  article

  Parametric Query Optimization (PQO) is an important problem in database systems, yet existing approaches suffer from high training costs, sensitivity to estimation errors, and vulnerability to severe performance regressions. This paper introduces PAR 2 QO (PARametric Penalty-Aware Robust Query Optimization), a system that integrates robust query optimization into PQO. PAR 2 QO strategically obtains plans from a well-balanced set of probe locations informed by the workload, and caches them as plan-penalty profiles. At runtime, PAR 2 QO selects the plan with the lowest expected penalty, explicitly accounting for selectivity uncertainties. Extensive experiments show that PAR 2 QO delivers significant speedups over existing methods while ensuring robustness against performance degradation. Additionally, we introduce CARVER , a workload generator aimed at covering possible cardinalities of subqueries. Not only does CARVER provide a more comprehensive way to evaluate PQO methods, but when used for training learned methods, it can also enhance their generalizability and stability.

  PublisherDOI

• Efficient Approximation Algorithm for Computing Wasserstein Barycenter under Euclidean Metric

  Society for Industrial and Applied Mathematics eBooks · 2025-01-01

  book-chapter1st authorCorresponding

  Given a set of probability distributions, the Wasserstein barycenter problem asks to compute a distribution that minimizes the average Wasserstein distance, or optimal transport cost, from all the input distributions. Wasserstein barycenters preserve common geometric features of the input distributions, making them useful in machine learning and data analytics tasks.

  PublisherDOI

• On Two-Handed Planar Assembly Partitioning with Connectivity Constraints

  ACM Transactions on Algorithms · 2025-01-10

  articleOpen access1st authorCorresponding

  Assembly planning is a fundamental problem in robotics and automation, which involves designing a sequence of motions to bring the separate constituent parts of a product into their final placement in the product. Assembly planning is naturally cast as a disassembly problem, giving rise to the assembly partitioning sub-problem: Given a set \(A\) of parts, find a subset \(S\subset A\) , referred to as a subassembly, such that \(S\) can be rigidly translated to infinity along a prescribed direction without colliding with \(A\setminus S\) . While assembly partitioning is efficiently solvable, it is further desirable for the parts of a subassembly to be easily held together. This motivates the problem that we study, called connected-assembly-partitioning , which additionally requires each of the two subassemblies, \(S\) and \(A\setminus S\) , to be connected. We obtain the following results. — We show that this problem is NP-complete, settling an open question posed by Wilson et al. 30 years ago, even when \(A\) consists of unit-grid squares (i.e., \(A\) is polyomino-shaped). For assemblies composed of polygons, we also show that deciding whether complete (dis)assembly is possible by repeatedly applying connected-assembly-partitioning, is NP-complete. Toward these results, we prove the NP-hardness of a new Planar 3-SAT variant having an adjacency requirement for variables appearing in the same clause, which may be of independent interest. — On the positive side, we give an \(O(2^{k}n^{2})\) -time fixed-parameter tractable algorithm (requiring low degree polynomial-time preprocessing) for an assembly \(A\) consisting of polygons in the plane, where \(n=|A|\) and \(k=|S|\) . We also describe a special case of unit-grid square assemblies, where a connected partition can always be found in \(O(n)\) -time.

  PublisherDOI

• Computing Instance-Optimal Kernels in Two Dimensions

  Discrete & Computational Geometry · 2024-04-07

  article1st author
  PublisherDOI

Recent grants

• AF:Medium:Collaborative Research: Uncertainty Aware Geometric Computing

  NSF · $316k · 2012–2016

• Collaborative Proposal: Motion -- Models, Algorithms, and Complexity

  NSF · $267k · 2002–2006

• AF: Large: Collaborative Research: Compact Representations and Efficient Algorithms for Distributed Geometric Data

  NSF · $449k · 2010–2015

• BSF:201229:Efficient Algorithms for Geometric Optimization

  NSF · $33k · 2013–2019

• Collaborative Rsearch: Large-Scale Analysis of Sensor Based Geometric Data

  NSF · $266k · 2007–2011

Frequent coauthors

• Micha Sharir

  Tel Aviv University

  236 shared

• Jiřı́ Matoušek

  Brno University of Technology

  51 shared

• Boris Aronov

  42 shared

• Sariel Har-Peled

  University of Illinois Urbana-Champaign

  39 shared

• Lars Arge

  Aarhus University

  34 shared

• Alon Efrat

  Alexandru Ioan Cuza University

  29 shared

• Subhash Suri

  University of California, Santa Barbara

  26 shared

• Ke Yi

  Hong Kong University of Science and Technology

  24 shared

Labs

• Pankaj K. Agarwal's LabPI

  Not provided

Awards & honors

• RJR Nabisco Distinguished Professor of Computer Science in T…
• Bass Fellow (2005 - Present)