Explanipedia

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

Pankaj K. Agarwal, Boris Aronov, Esther Ezra, Matthew J. Katz, Micha Sharir · 2025

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 fo…

On Two-Handed Planar Assembly Partitioning with Connectivity Constraints Open

Pankaj K. Agarwal, Boris Aronov, Tzvika Geft, Dan Halperin · 2025

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 natu…

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

Pankaj K. Agarwal, Boris Aronov, Guillaume Moroz · 2025

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 …

Line Intersection Searching Amid Unit Balls in 3-Space Open

Pankaj K. Agarwal, Esther Ezra · 2024

On Reporting Durable Patterns in Temporal Proximity Graphs Open

Pankaj K. Agarwal, Xiao Hu, Stavros Sintos, Jun Yang · 2024

Finding patterns in graphs is a fundamental problem in databases and data mining. In many applications, graphs are temporal and evolve over time, so we are interested in finding durable patterns, such as triangles and paths, which persist …

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

Pankaj K. Agarwal, Esther Ezra, Micha Sharir · 2024

Let $P$ be a set of $m$ points in ${\mathbb R}^2$, let $Σ$ be a set of $n$ semi-algebraic sets of constant complexity in ${\mathbb R}^2$, let $(S,+)$ be a semigroup, and let $w: P \rightarrow S$ be a weight function on the points of $P$. W…

Computing Data Distribution from Query Selectivities Open

Pankaj K. Agarwal, Rahul Raychaudhury, Stavros Sintos, Jun Yang · 2024

We are given a set 𝒵 = {(R_1,s_1), …, (R_n,s_n)}, where each R_i is a range in ℝ^d, such as rectangle or ball, and s_i ∈ [0,1] denotes its selectivity. The goal is to compute a small-size discrete data distribution 𝒟 = {(q₁,w₁),…, (q_m,w_m…

Program Committee Open

Amir Abboud, Pankaj K. Agarwal, Sepehr Assadi, Nikhil Bansal, Arnab Bhattacharyya , et al. · 2023

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

Pankaj K. Agarwal, Sharath Raghvendra, Pouyan Shirzadian, Keegan Yao · 2023

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 fr…

Fast Approximation Algorithms for Piercing Boxes by Points Open

Pankaj K. Agarwal, Sariel Har-Peled, Rahul Raychaudhury, Stavros Sintos · 2023

$\newcommand{\popt}{\mathcal{p}} \newcommand{\Re}{\mathbb{R}}\newcommand{\N}{\mathcal{N}} \newcommand{\BX}{\mathcal{B}} \newcommand{\bb}{\mathsf{b}} \newcommand{\eps}{\varepsilon} \newcommand{\polylog}{\mathrm{polylog}} $ Let $\mathcal{B}=…

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

Pankaj K. Agarwal, Esther Ezra, Micha Sharir · 2023

Vertical decomposition is a widely used general technique for decomposing the cells of arrangements of semi-algebraic sets in $d$-space into constant-complexity subcells. In this paper, we settle in the affirmative a few long-standing open…

On reverse shortest paths in geometric proximity graphs Open

Pankaj K. Agarwal, Matthew J. Katz, Micha Sharir · 2023

Computing Instance-Optimal Kernels in Two Dimensions Open

Pankaj K. Agarwal, Sariel Har-Peled · 2023

Let P be a set of n points in ℝ². 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 i…

Computing Complex Temporal Join Queries Efficiently Open

Xiao Hu, Stavros Sintos, Junyang Gao, Pankaj K. Agarwal, Jun Yang · 2022

This paper studies multi-way join queries over temporal data, where each tuple is associated with a valid time interval indicating when the tuple is valid. A temporal join requires that joining tuples' valid intervals intersect. Previous w…

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

Pankaj K. Agarwal, Boris Aronov, Esther Ezra, Matthew J. Katz, Micha Sharir · 2022

Let 𝒯 be a set of n planar semi-algebraic regions in ℝ³ of constant complexity (e.g., triangles, disks), which we call plates. We wish to preprocess 𝒯 into a data structure so that for a query object γ, which is also a plate, we can quickl…

Efficiently Answering Durability Prediction Queries Open

Junyang Gao, Yifan Xu, Pankaj K. Agarwal, Jun Yang · 2021

We consider a class of queries called durability prediction queries that arise commonly in predictive analytics, where we use a given predictive model to answer questions about possible futures to inform our decisions. Examples of durabili…

Dynamic Enumeration of Similarity Joins Open

Pankaj K. Agarwal, Xiao Hu, Stavros Sintos, Jun Yang · 2021

This paper considers enumerating answers to similarity-join queries under dynamic updates: Given two sets of $n$ points $A,B$ in $\mathbb{R}^d$, a metric $ϕ(\cdot)$, and a distance threshold $r > 0$, report all pairs of points $(a, b) \in …

Efficiently Answering Durability Prediction Queries Open

Junyang Gao, Yifan Xu, Pankaj K. Agarwal, Jun Yang · 2021

We consider a class of queries called durability prediction queries that arise commonly in predictive analytics, where we use a given predictive model to answer questions about possible futures to inform our decisions. Examples of durabili…

Durable Top-K Instant-Stamped Temporal Records with User-Specified Scoring Functions Open

Junyang Gao, Stavros Sintos, Pankaj K. Agarwal, Jun Yang · 2021

A way of finding interesting or exceptional records from instant-stamped temporal data is to consider their "durability," or, intuitively speaking, how well they compare with other records that arrived earlier or later, and how long they r…

On Two-Handed Planar Assembly Partitioning Open

Pankaj K. Agarwal, Boris Aronov, Tzvika Geft, Dan Halperin · 2021

Assembly planning, which is a fundamental problem in robotics and automation, aims to design a sequence of motions that will bring the separate constituent parts of a product into their final placement in the product. It is convenient to s…

An Output-Sensitive Algorithm for Computing the Union of Cubes and Fat Boxes in 3D Open

Pankaj K. Agarwal, Alex Steiger · 2021

Let C be a set of n axis-aligned cubes of arbitrary sizes in ℝ³. Let U be their union, and let κ be the number of vertices on ∂U; κ can vary between O(1) and O(n²). We show that U can be computed in O(n log³ n + κ) time if C is in general …

Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications Open

Pankaj K. Agarwal, Boris Aronov, Esther Ezra, Joshua Zahl · 2021

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…

Decomposing the Complement of the Union of Cubes in Three Dimensions Open

Pankaj K. Agarwal, Micha Sharir, Alex Steiger · 2021

1D and 2D Flow Routing on a Terrain Open

Aaron Lowe, Svend C. Svendsen, Pankaj K. Agarwal, Lars Arge · 2020

An important problem in terrain analysis is modeling how water flows across a\nterrain creating floods by forming channels and filling depressions. In this\npaper we study a number of \\emph{flow-query} related problems: Given a terrain\n$…

Dynamic geometric set cover and hitting set Open

Pankaj K. Agarwal, Hsien-Chih Chang, Subhash Suri, Allen Xiao, Jie Xue · 2020

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 thei…

Clustering Under Perturbation Stability in Near-Linear Time Open

Pankaj K. Agarwal, Hsien-Chih Chang, Kamesh Munagala, Erin Taylor, Emo Welzl · 2020

We consider the problem of center-based clustering in low-dimensional Euclidean spaces under the perturbation stability assumption. An instance is α-stable if the underlying optimal clustering continues to remain optimal even when all pair…

Dynamic Geometric Set Cover and Hitting Set Open

Pankaj K. Agarwal, Hsien-Chih Chang, Subhash Suri, Allen Xiao, Jie Xue · 2020

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 thei…

Management Training and Employment: An Empirical Analysis of Management Institutes Open

Pankaj K. Agarwal · 2020

The study seeks to identify those difficulties and offer novel perspectives on them as well as potential solutions. This research aims to quantify the perception gap between recruiters, academics, and MBA graduates with regards to the impo…

Theory of Reasoned Action and Organic Food Buying in India Open

Pankaj K. Agarwal · 2019

The purpose of this paper is to find out a relationship between attitude towards organic food, subjective norms and buying intention of organic food. This study explores the impact of attitude and subjective norms on buying intentions and …

Flood-Risk Analysis on Terrains under the Multiflow-Direction Model Open

Aaron Lowe, Pankaj K. Agarwal · 2019

An important problem in terrain analysis is modeling how water flows across a terrain and creates floods by filling up depressions. In this article, we study a number of flood-risk related problems: Given a terrain Σ, represented as a tria…

Pankaj K. Agarwal YOU? Author Swipe