About

Sariel Har-Peled is a Donald Biggar Willett Professor in Engineering at the University of Illinois Urbana-Champaign, affiliated with the Siebel School of Computing and Data Science. His research areas include Theory and Algorithms, with recent courses taught in algorithms and computational geometry. Har-Peled's work focuses on geometric approximation algorithms, randomized algorithms, and discrete and computational geometry. He has received recognition for his contributions to the field, including the Test of Time Award at STOC 2024. His research emphasizes the development of efficient algorithms for geometric problems, contributing significantly to the theoretical foundations of computational geometry and algorithms.

Research topics

• Computer Science
• Data Mining
• Artificial Intelligence
• Theoretical computer science
• Algorithm
• Mathematics

Selected publications

• Well-Separated Pairs Decomposition Revisited

  ArXiv.org · 2025-09-07

  preprintOpen access1st authorCorresponding

  We revisit the notion of WSPD (i.e., well-separated pairs-decomposition), presenting a new construction of WSPD for any finite metric space, and show that it is asymptotically instance-optimal in size. Next, we describe a new WSPD construction for the weighted unit-distance metric in the plane, and show a bound $O( \varepsilon^{-2} n \log n)$ on its size, improving by a factor of $1/\varepsilon^2$ over previous work. The new construction is arguably simpler and more elegant. We point out that using WSPD, one can approximate, in near-linear time, the distortion of a bijection between two point sets in low dimensions. As a new application of WSPD, we show how to shortcut a polygonal curve such that its dilation is below a prespecified quantity. In particular, we show a near-linear time algorithm for computing a simple subcurve for a given polygonal curve in the plane so that the new subcurve has no self-intersection.

  PublisherOA PDFDOI

• Faster Motion Planning via Restarts

  ArXiv.org · 2025-06-23

  preprintOpen accessSenior author

  Randomized methods such as PRM and RRT are widely used in motion planning. However, in some cases, their running-time suffers from inherent instability, leading to ``catastrophic'' performance even for relatively simple instances. We apply stochastic restart techniques, some of them new, for speeding up Las Vegas algorithms, that provide dramatic speedups in practice (a factor of $3$ [or larger] in many cases). Our experiments demonstrate that the new algorithms have faster runtimes, shorter paths, and greater gains from multi-threading (when compared with straightforward parallel implementation). We prove the optimality of the new variants. Our implementation is open source, available on github, and is easy to deploy and use.

  PublisherOA PDFDOI

• Efficiently Approximating the Minimum-Volume Bounding Box of a Point Set in Three Dimensions

  ArXiv.org · 2025-12-13

  preprintOpen accessSenior author

  $\renewcommand{\Re}{\mathbb{R}}$We present an efficient $O (n + 1/\varepsilon^{4.5})$-time algorithm for computing a $(1+\varepsilon$)-approximation of the minimum-volume bounding box of $n$ points in $\Re^3$. We also present a simpler algorithm (for the same purpose) whose running time is $O (n \log{n} + n / \varepsilon^3)$. We give some experimental results with implementations of various variants of the second algorithm. The implementation of the algorithm described in this paper is available online https://github.com/sarielhp/MVBB.

  PublisherOA PDFDOI

• Polygon Containment and Translational Min-Hausdorff-Distance between Segment Sets are 3SUM-Hard

  ArXiv.org · 2025-12-16 · 8 citations

  preprintOpen accessSenior author

  The 3SUM problem represents a class of problems conjectured to require $Ω(n^2)$ time to solve, where $n$ is the size of the input. Given two polygons $P$ and $Q$ in the plane, we show that some variants of the decision problem, whether there exists a transformation of $P$ that makes it contained in $Q$, are 3SUM-Hard. In the first variant $P$ and $Q$ are any simple polygons and the allowed transformations are translations only; in the second and third variants both polygons are convex and we allow either rotations only or any rigid motion. We also show that finding the translation in the plane that minimizes the Hausdorff distance between two segment sets is 3SUM-Hard.

  PublisherOA PDFDOI

• Bifurcation: How to Explore a Tree

  ArXiv.org · 2025-10-02

  preprintOpen access1st authorCorresponding

  Avraham et al. [AFK+15] presented an alternative approach to parametric search, called \emph{bifurcation}, that performs faster under certain circumstances. Intuitively, when the underlying decider execution can be rolled back cheaply and the decider has a near-linear running time. For some problems, this leads to fast algorithms that beat the seemingly natural lower bound arising from distance selection. Bifurcation boils down to a tree exploration problem. You are given a binary (unfortunately implicit) tree of height $n$ and $k$ internal nodes with two children (all other internal nodes have a single child), and assume each node has an associated parameter value. These values are sorted in the inorder traversal of the tree. Assume there is (say) a node (not necessarily a leaf) that is the target node that the exploration needs to discover. The player starts from the root. At each step, the player can move to adjacent nodes to the current location (i.e., one of the children or the parent). Alternatively, the player can call an oracle on the current node, which returns either that it is the target (thus, mission accomplished!) or whether the target value is strictly smaller or larger than the current one. A naive algorithm explores the whole tree, in $O(n k)$ time, then performs $O(\log k n)$ calls to the oracle to find the desired leaf. Avraham \etal showed that this can be improved to $O(n \sqrt{k} )$ time, and $O( \sqrt{k} \log n)$ oracle calls. Here, we improve this to $O(n \sqrt{k} )$ time, with only $ O( \sqrt{k} + \log n)$ oracle calls. We also show matching lower bounds, under certain assumptions. We believe our interpretation of bifurcation as a tree exploration problem, and the associated algorithm, are of independent interest.

  PublisherOA PDFDOI

• A Practical Approach for Computing the Diameter of a Point Set

  ArXiv.org · 2025-05-16

  preprintOpen access1st authorCorresponding

  We present an approximation algorithm for computing the diameter of a point-set in $\Re^d$. The new algorithm is sensitive to the ``hardness'' of computing the diameter of the given input, and for most inputs it is able to compute the exact diameter extremely fast. The new algorithm is simple, robust, has good empirical performance, and can be implemented quickly. As such, it seems to be the algorithm of choice in practice for computing/approximating the diameter.

  PublisherOA PDFDOI

• Improving the average dilation of a metric graph by adding edges

  ArXiv.org · 2025-05-30

  preprintOpen access1st authorCorresponding

  For a graph $G$ spanning a metric space, the dilation of a pair of points is the ratio of their distance in the shortest path graph metric to their distance in the metric space. Given a graph $G$ and a budget $k$, a classic problem is to augment $G$ with $k$ additional edges to reduce the maximum dilation. In this note, we consider a variant of this problem where the goal is to reduce the average dilation for pairs of points in $G$. We provide an $O(k)$ approximation algorithm for this problem, matching the approximation ratio given by prior work for the maximum dilation variant.

  PublisherOA PDFDOI

• Orthogonal Emptiness Queries for Random Points

  ArXiv.org · 2025-05-09

  preprintOpen accessSenior author

  We present a data-structure for orthogonal range searching for random points in the plane. The new data-structure uses (in expectation) $O\bigl(n \log n ( \log \log n)^2 \bigr)$ space, and answers emptiness queries in constant time. As a building block, we construct a data-structure of expected linear size, that can answer predecessor/rank queries, in constant time, for random numbers sampled uniformly from $[0,1]$. While the basic idea we use is known [Dev89], we believe our results are still interesting.

  PublisherOA PDFDOI

• Edge Nearest Neighbor in Sampling-Based Motion Planning

  ArXiv.org · 2025-06-16

  preprintOpen accessSenior author

  Neighborhood finders and nearest neighbor queries are fundamental parts of sampling based motion planning algorithms. Using different distance metrics or otherwise changing the definition of a neighborhood produces different algorithms with unique empiric and theoretical properties. In \cite{l-pa-06} LaValle suggests a neighborhood finder for the Rapidly-exploring Random Tree RRT algorithm \cite{l-rrtnt-98} which finds the nearest neighbor of the sampled point on the swath of the tree, that is on the set of all of the points on the tree edges, using a hierarchical data structure. In this paper we implement such a neighborhood finder and show, theoretically and experimentally, that this results in more efficient algorithms, and suggest a variant of the Rapidly-exploring Random Graph RRG algorithm \cite{f-isaom-10} that better exploits the exploration properties of the newly described subroutine for finding narrow passages.

  PublisherOA PDFDOI

• An Easy Proof of a Weak Version of Chernoff inequality

  ArXiv.org · 2025-07-03

  preprintOpen access1st authorCorresponding

  We prove an easy but very weak version of Chernoff inequality. Namely, that the probability that in $6M$ throws of a fair coin, one gets at most $M$ heads is $\leq 1/2^M$.

  PublisherOA PDFDOI

Recent grants

• CAREER: Approximation Algorithms for Geometric Computing

  NSF · $325k · 2002–2008

• AF: Small: Efficient Proximity and Similarity Search in Computational Geometry

  NSF · $489k · 2012–2017

• AF: Small: Towards Sturdier Geometric Algorithms

  NSF · $400k · 2019–2023

• AF: Small: Approximation, Covering and Clustering in Computational Geometry

  NSF · $410k · 2009–2013

• AF: Small: Towards better geometric algorithms: Summarizing, partitioning and shrinking data

  NSF · $490k · 2014–2019

Frequent coauthors

• Micha Sharir

  Tel Aviv University

  45 shared

• Pankaj K. Agarwal

  39 shared

• Anne Driemel

  Hausdorff Center for Mathematics

  33 shared

• Benjamin Raichel

  32 shared

• Mitchell Jones

  31 shared

• Nirman Kumar

  University of Memphis

  25 shared

• Timothy M. Chan

  University of Illinois Urbana-Champaign

  23 shared

• Sepideh Mahabadi

  16 shared

Labs

• Theory and AlgorithmsPI

Awards & honors

• Test of Time Award at STOC 2024