Sariel Har-Peled

$\renewcommand{\Re}{\mathbb{R}}$Recent work showed how to construct nearest-neighbor graphs of linear size, on a given set $P$ of $n$ points in $\Re^d$, such that one can answer approximate nearest-neighbor queries in logarithmic time in the spread. Unfortunately, the spread might be unbounded in $n$, and an interesting theoretical question is how to remove the dependency on the spread. Here, we show how to construct an external linear-size data structure that, combined with the linear-size graph, allows us to answer ANN queries in logarithmic time in $n$.

$\newcommand{\Re}{\mathbb{R}}$We study the minWSPD problem of computing the minimum-size well-separated pairs decomposition of a set of points, and show constant approximation algorithms in low-dimensional Euclidean space and doubling metrics. This problem is computationally hard already $\Re^2$, and is also hard to approximate. We also introduce a new pair decomposition, removing the requirement that the diameters of the parts should be small. Surprisingly, we show that in a general metric space, one can compute such a decomposition of size $O( \tfrac{n}{\varepsilon}\log n)$, which is dramatically smaller than the quadratic bound for WSPDs. In $\Re^d$, the bound improves to $O( d \tfrac{n}{\varepsilon}\log \tfrac{1}{\varepsilon } )$.

$\renewcommand{\Re}{\mathbb{R}}\newcommand{\eps}{\varepsilon}\newcommand{\poly}{\mathrm{poly}} $In this paper, we study the problem of $L_1$-fitting a shape to a set of $n$ points in $\Re^d$ (where $d$ is a fixed constant), where the target is to minimize the sum of distances of the points to the shape, or the sum of squared distances. We present a general technique for computing a $(1 + \eps ) $-approximation for such a problem, with running time $O(n + \poly( \log n, 1/\eps))$, where $\poly(\log n, 1/\eps)$ is a polynomial of constant degree of $\log n$ and $1/\eps$ (the power of the polynomial is a function of $d$). The new algorithm runs in linear time for a fixed $\eps>0$, and is the first subquadratic algorithm for this problem. Applications of the algorithm include best fitting either a circle, a sphere, or a cylinder to a set of points when minimizing the sum of distances (or squared distances) to the respective shape.

$\def\DD{\bf δ}\def\CH{\mathop{\mathrm{ConvexHull}}}\newcommand{\LL}{\cal {L}} \newcommand{\ZZ}{\mathbb{Z}} $ Given a convex body $C$ in the plane, its discrete hull is $C^0 = \CH( C \cap \LL )$, where $\LL = \ZZ \times \ZZ$ is the integer lattice. We present an $O( |C^0| \log \DD(C) )$-time algorithm for calculating the discrete hull of $C$, where $|C^0|$ denotes the number of vertices of $C^0$, and $\DD(C)$ is the diameter of $C$. Actually, using known combinatorial bounds, the running time of the algorithm is $O(\DD(C)^{2/3} \log{\DD(C)})$. In particular, this bound applies when $C$ is a disk.

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.

$\renewcommand{\Re}{\mathbb{R}}$We present a new optimal construction of a semi-separated pair decomposition (i.e., SSPD) for a set of $n$ points in $\Re^d$. In the new construction each point participates in a few pairs, and it extends easily to spaces with low doubling dimension. This is the first optimal construction with these properties. As an application of the new construction, for a fixed $t>1$, we present a new construction of a $t$-spanner with $O(n)$ edges and maximum degree $O(\log^2 n)$ that has a separator of size $O\pth{n^{1-1/d}}$.

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.

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.