
Given $n$ pairwise openly disjoint triangles in 3space, their vertical depth
relation may contain cycles. We show that, for any $\varepsilon>0$, the
triangles can be cut into $O(n^{3/2+\varepsilon})$ connected semialgebraic
pieces, whose description complexity depends only on the choice of
$\varepsilon$, such that the depth relation among these pieces is now a proper
partial order. This bound is nearly tight in the worst case. We are not aware
of any previous study of this problem, in this full generality, with a
subquadratic bound on the number of pieces.
This work extends the recent study by two of the authors (Aronov,
Sharir~2018) on eliminating depth cycles among lines in 3space. Our approach
is again algebraic, and makes use of a recent variant of the polynomial
partitioning technique, due to Guth, which leads to a recursive procedure for
cutting the triangles. In contrast to the case of lines, our analysis here is
considerably more involved, due to the twodimensional nature of the objects
being cut, so additional tools, from topology and algebra, need to be brought
to bear.
Our result essentially settles a 35yearold open problem in computational
geometry, motivated by hiddensurface removal in computer graphics.

We present an explicit and efficient construction of additively weighted
Voronoi diagrams on planar graphs. Let $G$ be a planar graph with $n$ vertices
and $b$ sites that lie on a constant number of faces. We show how to preprocess
$G$ in $\tilde O(nb^2)$ time so that one can compute any additively weighted
Voronoi diagram for these sites in $\tilde O(b)$ time.
We use this construction to compute the diameter of a directed planar graph
with real arc lengths in $\tilde{O}(n^{5/3})$ time. This improves the recent
breakthrough result of Cabello (SODA'17), both by improving the running time
(from $\tilde{O}(n^{11/6})$), and by providing a deterministic algorithm. It is
in fact the first truly subquadratic deterministic algorithm for this problem.
Our use of Voronoi diagrams to compute the diameter follows that of Cabello,
but he used abstract Voronoi diagrams, which makes his diameter algorithm more
involved, more expensive, and randomized.
As in Cabello's work, our algorithm can also compute the Wiener index of a
planar graph (i.e., the sum of all pairwise distances) within the same bound.
Our construction of Voronoi diagrams for planar graphs is of independent
interest. It has already been used to obtain fast exact distance oracles for
planar graphs [CohenAddad et al., FOCS'17].

We present an $O(n)$ expected time algorithm and an $O(n \log n)$
deterministic time algorithm to find a set of five points that stab a set of
$n$ pairwise intersecting disks in the plane. We also give a simple
construction with 13 pairwise intersecting disks that cannot be stabbed by
three points.

We consider problems involving rich homotheties in a set S of n points in the
plane (that is, homotheties that map many points of S to other points of S). By
reducing these problems to incidence problems involving points and lines in
R^3, we are able to obtain refined and new bounds for the number of rich
homotheties, and for the number of distinct equivalence classes, under
homotheties, of kelement subsets of S, for any k >= 3. We also discuss the
extensions of these problems to three and higher dimensions.

Given a set $S$ of $n$ points in $\mathbb{R}^d$, the Closest Pair problem is
to find a pair of distinct points in $S$ at minimum distance. When $d$ is
constant, there are efficient algorithms that solve this problem, and fast
approximate solutions for general $d$. However, obtaining an exact solution in
very high dimensions seems to be much less understood. We consider the
highdimensional $L_\infty$ Closest Pair problem, where $d=n^r$ for some $r >
0$, and the underlying metric is $L_\infty$.
We improve and simplify previous results for $L_\infty$ Closest Pair, showing
that it can be solved by a deterministic stronglypolynomial algorithm that
runs in $O(DP(n,d)\log n)$ time, and by a randomized algorithm that runs in
$O(DP(n,d))$ expected time, where $DP(n,d)$ is the time bound for computing the
{\em dominance product} for $n$ points in $\mathbb{R}^d$. That is a matrix $D$,
such that $D[i,j] = \bigl \{k \mid p_i[k] \leq p_j[k]\} \bigr$; this is the
number of coordinates at which $p_j$ dominates $p_i$. For integer coordinates
from some interval $[M, M]$, we obtain an algorithm that runs in
$\tilde{O}\left(\min\{Mn^{\omega(1,r,1)},\, DP(n,d)\}\right)$ time, where
$\omega(1,r,1)$ is the exponent of multiplying an $n \times n^r$ matrix by an
$n^r \times n$ matrix.
We also give slightly better bounds for $DP(n,d)$, by using more recent
rectangular matrix multiplication bounds. Computing the dominance product
itself is an important task, since it is applied in many algorithms as a major
blackbox ingredient, such as algorithms for APBP (all pairs bottleneck paths),
and variants of APSP (all pairs shortest paths).

In this paper we establish an improved bound for the number of incidences
between a set $P$ of $m$ points and a set $H$ of $n$ planes in $\mathbb R^3$,
provided that the points lie on a twodimensional nonlinear irreducible
algebraic variety $V$ of constant degree. Specifically, the bound is $$ O\left(
m^{2/3}n^{2/3} + m^{6/11}n^{9/11}\log^\beta(m^3/n) + m + n + \sum_\ell
P_\ell\cdot H_\ell \right) , $$ where the constant of proportionality and
the constant exponent $\beta$ depend on the degree of $V$, and where the sum
ranges over all lines $\ell$ that are fully contained in $V$ and contain at
least one point of $P$, so that, for each such $\ell$, $P_\ell = P\cap\ell$ and
$H_\ell$ is the set of the planes of H that contain $\ell$. In addition,
$\sum_\ell P_\ell = O(m)$ and $\sum_\ell H_\ell = O(n)$.
This improves, for this special case, the earlier more general bound of
Apfelbaum and Sharir (see also Brass and Knauer as well as Elekes and T\'oth).
This is a generalization of the incidence bound for points and circles in the
plane (cf. Aronov et al., Aronov and Sharir, Marcus and Tardos), and is based
on a recent result of Sharir and Zahl on the number of cuts that turn a
collection of algebraic curves into pseudosegments.
The case where $V$ is a quadric is simpler to analyze, does not require the
result of Sharir and Zahl, and yields the same bound as above, with
$\beta=2/11$.
We present an interesting application of our results to a problem, studied by
Rudnev, on obtaining a lower bound on the number of distinct crossratios
determined by $n$ real points, where our bound leads to a slight improvement in
Rudnev's bound.

We study a wide spectrum of incidence problems involving points and curves or
points and surfaces in $\mathbb R^3$. The current (and in fact the only viable)
approach to such problems, pioneered by Guth and Katz [2010,2015], requires a
variety of tools from algebraic geometry, most notably (i) the polynomial
partitioning technique, and (ii) the study of algebraic surfaces that are ruled
by lines or, in more recent studies [GuthZahl 2016], by algebraic curves of
some constant degree. By exploiting and refining these tools, we obtain new and
improved bounds for numerous incidence problems in $\mathbb R^3$. In broad
terms, we consider two kinds of problems, those involving points and
constantdegree algebraic \emph{curves}, and those involving points and
constantdegree algebraic \emph{surfaces}. In some variants we assume that the
points lie on some fixed constantdegree algebraic variety, and in others we
consider arbitrary sets of points in 3space. our results provide a "grand
generalization" of most of the previous studies of (special instances of)
previous works for both curves and surfaces.
As an application of our pointcurve incidence bound, we consider the problem
of bounding the number of similar triangles spanned by a set of $n$ points in
$\mathbb R^3$, and obtain the bound $O(n^{15/7}),$ thus improving the bound of
Agarwal et al [2007].
As applications of our pointsurface incidence bounds, we consider the
problems of distinct and repeated distances determined by a set of $n$ points
in $\mathbb R^3$, two of the most celebrated open problems in combinatorial
geometry. We obtain new and improved bounds for two special cases, one in which
the points lie on some algebraic variety of constant degree, and one involving
incidences between pairs in $P_1\times P_2$, where $P_1$ is contained in a
variety and $P_2$ is arbitrary.

Given a set of $n$ real numbers, the 3SUM problem is to decide whether there
are three of them that sum to zero. Until a recent breakthrough by Gr{\o}nlund
and Pettie [FOCS'14], a simple $\Theta(n^2)$time deterministic algorithm for
this problem was conjectured to be optimal. Over the years many algorithmic
problems have been shown to be reducible from the 3SUM problem or its variants,
including the more generalized forms of the problem, such as $k$SUM and
$k$variate linear degeneracy testing ($k$LDT). The conjectured hardness of
these problems have become extremely popular for basing conditional lower
bounds for numerous algorithmic problems in P.
In this paper, we show that the randomized $4$linear decision tree
complexity of 3SUM is $O(n^{3/2})$, and that the randomized $(2k2)$linear
decision tree complexity of $k$SUM and $k$LDT is $O(n^{k/2})$, for any odd
$k\ge 3$. These bounds improve (albeit randomized) the corresponding
$O(n^{3/2}\sqrt{\log n})$ and $O(n^{k/2}\sqrt{\log n})$ decision tree bounds
obtained by Gr{\o}nlund and Pettie. Our technique includes a specialized
randomized variant of fractional cascading data structure. Additionally, we
give another deterministic algorithm for 3SUM that runs in $O(n^2 \log\log n /
\log n )$ time. The latter bound matches a recent independent bound by Freund
[Algorithmica 2017], but our algorithm is somewhat simpler, due to a better use
of wordRAM model.

We consider the number of distinct distances between two finite sets of
points in ${\bf R}^k$, for any constant dimension $k\ge 2$, where one set $P_1$
consists of $n$ points on a line $l$, and the other set $P_2$ consists of $m$
arbitrary points, such that no hyperplane orthogonal to $l$ and no
hypercylinder having $l$ as its axis contains more than $O(1)$ points of $P_2$.
The number of distinct distances between $P_1$ and $P_2$ is then $$
\Omega\left(\min\left\{ n^{2/3}m^{2/3},\;
\frac{n^{10/11}m^{4/11}}{\log^{2/11}m},\; n^2,\; m^2\right\}\right) . $$
Without the assumption on $P_2$, there exist sets $P_1$, $P_2$ as above, with
only $O(m+n)$ distinct distances between them.

Dynamic Time Warping (DTW) and Geometric Edit Distance (GED) are basic
similarity measures between curves or general temporal sequences (e.g., time
series) that are represented as sequences of points in some metric space $(X,
\mathrm{dist})$. The DTW and GED measures are massively used in various fields
of computer science, computational biology, and engineering. Consequently, the
tasks of computing these measures are among the core problems in P. Despite
extensive efforts to find more efficient algorithms, the bestknown algorithms
for computing the DTW or GED between two sequences of points in $X =
\mathbb{R}^d$ are longstanding dynamic programming algorithms that require
quadratic runtime, even for the onedimensional case $d = 1$, which is perhaps
one of the most used in practice.
In this paper, we break the nearly 50 years old quadratic time bound for
computing DTW or GED between two sequences of $n$ points in $\mathbb{R}$, by
presenting deterministic algorithms that run in $O\left( n^2 / \log\log n
\right)$ time. Our algorithms can be extended to work also for higher
dimensional spaces $\mathbb{R}^d$, for any constant $d$, when the underlying
distancemetric $\mathrm{dist}$ is polyhedral (e.g., $L_1, L_\infty$).

Let $F\in\mathbb{C}[x,y,s,t]$ be an irreducible constantdegree polynomial,
and let $A,B,C,D\subset\mathbb{C}$ be finite sets of size $n$. We show that $F$
vanishes on at most $O(n^{8/3})$ points of the Cartesian product $A\times
B\times C\times D$, unless $F$ has a special grouprelated form. A similar
statement holds for $A,B,C,D$ of unequal sizes. This is a fourdimensional
extension of our recent improved analysis of the original ElekesSzab\'o
theorem in three dimensions. We give three applications: an expansion bound for
threevariable real polynomials that do not have a special form, a bound on the
number of coplanar quadruples on a space curve that is neither planar nor
quartic, and a bound on the number of fourpoint circles on a plane curve that
has degree at least five.

Let $P$ be a set of $m$ points and $L$ a set of $n$ lines in $\mathbb R^4$,
such that the points of $P$ lie on an algebraic threedimensional surface of
degree $D$ that does not contain hyperplane or quadric components, and no
2flat contains more than $s$ lines of $L$. We show that the number of
incidences between $P$ and $L$ is $$ I(P,L) = O\left(m^{1/2}n^{1/2}D +
m^{2/3}n^{1/3}s^{1/3} + nD + m\right) , $$ for some absolute constant of
proportionality. This significantly improves the bound of the authors, for
arbitrary sets of points and lines in $\mathbb R^4$, when $D$ is not too large.
The same bound holds when the threedimensional surface is embedded in any
higher dimensional space. For the proof of this bound, we revisit certain parts
of [SharirSolomon16], combined with the following new incidence bound. Let $P$
be a set of $m$ points and $L$ a set of $n$ lines in $\mathbb R^d$, for $d\ge
3$, which lie in a common twodimensional algebraic surface of degree $D$
(assumed to be $\ll n^{1/2}$) that does not contain any 2flat, so that no
2flat contains more than $s$ lines of $L$ (here we require that the lines of
$L$ also be contained in the surface). Then the number of incidences between
$P$ and $L$ is $$ I(P,L) = O\left(m^{1/2}n^{1/2}D^{1/2} + m^{2/3}D^{2/3}s^{1/3}
+ m + n\right). $$ When $d=3$, this improves the bound of Guth and Katz for
this special case, when $D \ll n^{1/2}$. Moreover, the bound does not involve
the term $O(nD)$, that arises in most standard approaches, and its removal is a
significant aspect of our result. Finally, we also obtain (slightly weaker)
variants of both results over the complex field. For twodimensional varieties,
the bound is as in the real case, with an added term of $O(D^3)$. For
threedimensional varieties, the bound is as in the real case, with an added
term of $O(D^6)$.

Let $H$ be a set of $n$ halfplanes in $\mathbb{R}^2$ in general position, and
let $k<n$ be a given parameter. We show that the number of vertices of the
arrangement of $H$ that lie at depth exactly $k$ (i.e., that are contained in
the interiors of exactly $k$ halfplanes of $H$) is $O(nk^{1/3} +
n^{2/3}k^{4/3})$. The bound is tight when $k=\Theta(n)$. This generalizes the
study of Dey [Dey98], concerning the complexity of a single level in an
arrangement of lines, and coincides with it for $k=O(n^{1/3})$.

The \emph{Fr\'echet distance} is a well studied similarity measures between
curves. The \emph{discrete Fr\'echet distance} is an analogous similarity
measure, defined for a sequence $A$ of $m$ points and a sequence $B$ of $n$
points, where the points are usually sampled from input curves. In this paper
we consider a variant, called the \emph{discrete Fr\'echet distance with
shortcuts}, which captures the similarity between (sampled) curves in the
presence of outliers. For the \emph{twosided} case, where shortcuts are
allowed in both curves, we give an $O((m^{2/3}n^{2/3}+m+n)\log^3 (m+n))$time
algorithm for computing this distance. When shortcuts are allowed only in one
noisecontaining curve, we give an even faster randomized algorithm that runs
in $O((m+n)^{6/5+\varepsilon})$ expected time, for any $\varepsilon>0$.
Our techniques are novel and may find further applications. One of the main
new technical results is: Given two sets of points $A$ and $B$ and an interval
$I$, we develop an algorithm that decides whether the number of pairs $(x,y)\in
A\times B$ whose distance ${\rm dist}(x,y)$ is in $I$, is less than some given
threshold $L$. The running time of this algorithm decreases as $L$ increases.
In case there are more than $L$ pairs of points whose distance is in $I$, we
can get a small sample of pairs that contains a pair at approximate median
distance (i.e., we can approximately "bisect" $I$). We combine this procedure
with additional ideas to search, with a small overhead, for the optimal
onesided Fr\'echet distance with shortcuts, using a very fast decision
procedure. We also show how to apply this technique for approximating distance
selection (with respect to rank), and for computing the semicontinuous
Fr\'echet distance with onesided shortcuts.

Following a recent improvement of Cardinal et al. on the complexity of a
linear decision tree for $k$SUM, resulting in $O(n^3 \log^3{n})$ linear
queries, we present a further improvement to $O(n^2 \log^2{n})$ such queries.

Let $p_1,p_2,p_3$ be three distinct points in the plane, and, for $i=1,2,3$,
let $\mathcal C_i$ be a family of $n$ unit circles that pass through $p_i$. We
address a conjecture made by Sz\'ekely, and show that the number of points
incident to a circle of each family is $O(n^{11/6})$, improving an earlier
bound for this problem due to Elekes, Simonovits, and Szab\'o [Combin. Probab.
Comput., 2009]. The problem is a special instance of a more general problem
studied by Elekes and Szab\'o [Combinatorica, 2012] (and by Elekes and R\'onyai
[J. Combin. Theory Ser. A, 2000]).

Given $n$ nonvertical lines in 3space, their vertical depth (above/below)
relation can contain cycles. We show that the lines can be cut into
$O(n^{3/2}\mathop{\mathrm{polylog}} n)$ pieces, such that the depth relation
among these pieces is now a proper partial order. This bound is nearly tight in
the worst case.
Previous results on this topic could only handle restricted cases of the
problem (such as handling only triangular cycles, by Aronov, Koltun, and Sharir
(2005), or only cycles in gridlike patterns, by Chazelle et al. (1992)), and
the bounds were considerably weakermuch closer to the trivial quadratic
bound.
Our proof uses a recent variant of the polynomial partitioning technique, due
to Guth, and some simple tools from algebraic geometry. It is much more
straightforward than the previous "purely combinatorial" methods.
Our technique can be extended to eliminating all cycles in the depth relation
among segments, and among constantdegree algebraic arcs. We hope that a
suitable extension of this technique could be used to handle the much more
difficult case of pairwisedisjoint triangles.
We also discuss several algorithms for constructing a small set of cuts so as
to eliminate all depthrelation cycles among the lines (minimizing such a set,
for the case of line segments, is known to be NPcomplete). The performance of
these algorithms improves due to our new bound, but, so far, none of them both
(a) produce close to $n^{3/2}$ cuts, and (b) run in time close to $n^{3/2}$, in
the worst case.
Our results almost completely settle a 35yearold open problem in
computational geometry, motivated by hiddensurface removal in computer
graphics.

$\renewcommand{\Re}{{\rm I\!\hspace{0.025em} R}}
\newcommand{\SetX}{\mathsf{X}} \newcommand{\eps}{\varepsilon}
\newcommand{\VorX}[1]{\mathcal{V} \pth{#1}} \newcommand{\Polygon}{\mathsf{P}}
\newcommand{\IntRange}[1]{[ #1 ]} \newcommand{\Space}{\ovebarline{\mathsf{m}}}
\newcommand{\pth}[2][\!]{#1\left({#2}\right)} \newcommand{\Arr}{{\cal A}}$
Let $H$ be a set of $n$ planes in three dimensions, and let $r \leq n$ be a
parameter. We give a simple alternative proof of the existence of a
$(1/r)$cutting of the first $n/r$ levels of $\Arr(H)$, which consists of
$O(r)$ semiunbounded vertical triangular prisms. The same construction yields
an approximation of the $(n/r)$level by a terrain consisting of $O(r/\eps^3)$
triangular faces, which lies entirely between the levels $(1\pm\eps)n/r$. The
proof does not use sampling, and exploits techniques based on planar separators
and various structural properties of levels in threedimensional arrangements
and of planar maps. The proof is constructive, and leads to a simple randomized
algorithm, with expected nearlinear running time. An application of this
technique allows us to mimic Matousek's construction of cuttings in the plane,
to obtain a similar construction of "layered" $(1/r)$cutting of the entire
arrangement $\Arr(H)$, of optimal size $O(r^3)$. Another application is a
simplified optimal approximate range counting algorithm in three dimensions,
competing with that of Afshani and Chan.

We show that a set of $n$ algebraic plane curves of constant maximum degree
can be cut into $O(n^{3/2}\operatorname{polylog} n)$ Jordan arcs, so that each
pair of arcs intersect at most once, i.e., they form a collection of
pseudosegments. This extends a similar (and slightly better) bound for
pseudocircles due to Marcus and Tardos. Our result is based on a technique of
Ellenberg, Solymosi and Zahl that transforms arrangements of plane curves into
arrangements of space curves, so that lenses (pairs of subarcs of the curves
that intersect at least twice) become vertical depth cycles. We then apply a
variant of a technique of Aronov and Sharir to eliminate these depth cycles by
making a small number of cuts, which corresponds to a small number of cuts to
the original planar arrangement of curves. After these cuts have been
performed, the resulting curves form a collection of pseudosegments.
Our cutting bound leads to new incidence bounds between points and
constantdegree algebraic curves. The conditions for these incidence bounds are
slightly stricter than those for the current bestknown bound of Pach and
Sharir; for our result to hold, the curves must be algebraic and of bounded
maximum degree, while Pach and Sharir's bound only imposes weaker, purely
topological constraints on the curves. However, when our conditions hold, the
new bounds are superior for almost all ranges of parameters. We also obtain new
bounds on the complexity of a single level in an arrangement of constantdegree
algebraic curves, and a new bound on the complexity of many marked faces in an
arrangement of such curves.

We describe a new data structure for dynamic nearest neighbor queries in the
plane with respect to a general family of distance functions. These include
$L_p$norms and additively weighted Euclidean distances. Our data structure
supports general (convex, pairwise disjoint) sites that have constant
description complexity (e.g., points, line segments, disks, etc.). Our
structure uses $O(n \log^3 n)$ storage, and requires polylogarithmic update and
query time, improving an earlier data structure of Agarwal, Efrat and Sharir
that required $O(n^\varepsilon)$ time for an update and $O(\log n)$ time for a
query [SICOMP, 1999]. Our data structure has numerous applications. In all of
them, it gives faster algorithms, typically reducing an $O(n^\varepsilon)$
factor in the previous bounds to polylogarithmic. In addition, we give here two
new applications: an efficient construction of a spanner in a disk intersection
graph, and a data structure for efficient connectivity queries in a dynamic
disk graph.

In this paper we show that the number of distinct distances determined by a
set of $n$ points on a constantdegree twodimensional algebraic variety $V$
(i.e., a surface) in $\mathbb R^3$ is at least $\Omega\left(n^{7/9}/{\rm
polylog} \,n\right)$. This bound is significantly larger than the conjectured
bound $\Omega(n^{2/3})$ for general point sets in $\mathbb R^3$.
We also show that the number of unit distances determined by $n$ points on a
surface $V$, as above, is $O(n^{4/3})$, a bound that matches the best known
planar bound, and is worstcase tight in 3space. This is in sharp contrast
with the best known general bound $O(n^{3/2})$ for points in three dimensions.
To prove these results, we establish an improved upper bound for the number
of incidences between a set $P$ of $m$ points and a set $S$ of $n$ spheres, of
arbitrary radii, in $\mathbb R^3$, provided that the points lie on an algebraic
surface $V$ of constant degree, which does not have linear or spherical
components. Specifically, the bound is $$ O\left( m^{2/3}n^{2/3} +
m^{1/2}n^{7/8}\log^\beta(m^4/n) + m + n + \sum_{c} P_{c}\cdot S_{c} \right)
, $$ where the constant of proportionality and the constant exponent $\beta$
depend on the degree of $V$, and where the sum ranges over all circles $c$ that
are fully contained in $V$, so that, for each such $c$, $P_c = P\cap c$ and
$S_c$ is the set of the spheres of $S$ that contain $c$. In addition, $\sum_{c}
P_{c} = O(m)$ and $\sum_{c} S_{c} = O(n)$. This bound too improves upon
earlier known bounds. These have been obtained for arbitrary point sets but
only under severe restrictions about the spheres, which are dropped in our
result. Another interesting application of our result is an incidence bound for
arbitrary points and spheres in 3space, where we improve and generalize the
previous work of Apfelbaum and Sharir[AS].

We generalize the Szemer\'ediTrotter incidence theorem, to bound the number
of complete \emph{flags} in higher dimensions. Specifically, for each
$i=0,1,\ldots,d1$, we are given a finite set $S_i$ of $i$flats in $\R^d$ or
in $\C^d$, and a (complete) flag is a tuple $(f_0,f_1,\ldots,f_{d1})$, where
$f_i\in S_i$ for each $i$ and $f_i\subset f_{i+1}$ for each $i=0,1,\ldots,d2$.
Our main result is an upper bound on the number of flags which is tight in the
worst case.
We also study several other kinds of incidence problems, including (i)
incidences between points and lines in $\R^3$ such that among the lines
incident to a point, at most $O(1)$ of them can be coplanar, (ii) incidences
with Legendrian lines in $\R^3$, a special class of lines that arise when
considering flags that are defined in terms of other groups, and (iii) flags in
$\R^3$ (involving points, lines, and planes), where no given line can contain
too many points or lie on too many planes. The bound that we obtain in (iii) is
nearly tight in the worst case.
Finally, we explore a group theoretic interpretation of flags, a generalized
version of which leads us to new incidence problems.

We show that for $m$ points and $n$ lines in the real plane, the number of
distinct distances between the points and the lines is
$\Omega(m^{1/5}n^{3/5})$, as long as $m^{1/2}\le n\le m^2$. We also prove that
for any $m$ points in the plane, not all on a line, the number of distances
between these points and the lines that they span is $\Omega(m^{4/3})$. The
problem of bounding the number of distinct pointline distances can be reduced
to the problem of bounding the number of tangent pairs among a finite set of
lines and a finite set of circles in the plane, and we believe that this latter
question is of independent interest. In the same vein, we show that $n$ circles
in the plane determine at most $O(n^{3/2})$ points where two or more circles
are tangent, improving the previously best known bound of $O(n^{3/2}\log n)$.
Finally, we study threedimensional versions of the distinct pointline
distances problem, namely, distinct pointline distances and distinct
pointplane distances. The problems studied in this paper are all new, and the
bounds that we derive for them, albeit most likely not tight, are nontrivial
to prove. We hope that our work will motivate further studies of these and
related problems.

We prove that the number of incidences between $m$ points and $n$
boundeddegree curves with $k$ degrees of freedom in ${\mathbb R}^d$ is \[
I(m,n) =O\left(m^{\frac{k}{dkd+1}+\varepsilon}n^{\frac{dkd}{dkd+1}}+
\sum_{j=2}^{d1}
m^{\frac{k}{jkj+1}+\varepsilon}n^{\frac{d(j1)(k1)}{(d1)(jkj+1)}}q_j^{\frac{(dj)(k1)}{(d1)(jkj+1)}}+m+n\right),
\] for any $\varepsilon>0$, where the constant of proportionality depends on
$k, \varepsilon$ and $d$, provided that no $j$dimensional surface of degree
$\le c_j(k,d,\varepsilon)$, a constant parameter depending on $k$, $d$, $j$,
and $\varepsilon$, contains more than $q_j$ input curves, and that the $q_j$'s
satisfy certain mild conditions.
This bound generalizes a recent result of Sharir and Solomon concerning
pointline incidences in four dimensions (where $d=4$ and $k=2$), and partly
generalizes a recent result of Guth (as well as the earlier bound of Guth and
Katz) in three dimensions (Guth's threedimensional bound has a better
dependency on $q_2$). It also improves a recent $d$dimensional general
incidence bound by Fox, Pach, Sheffer, Suk, and Zahl, in the special case of
incidences with algebraic curves. Our results are also related to recent works
by Dvir and Gopi and by Hablicsek and Scherr concerning rich lines in
highdimensional spaces.

The Delaunay triangulation (DT) is one of the most common and useful
triangulations of point sets $P$ in the plane. DT is not unique when $P$ is
degenerate, specifically when it contains quadruples of cocircular points. One
way to achieve uniqueness is by applying a small (or infinitesimal)
perturbation to $P$.
We consider a specific perturbation of such degenerate sets, in which the
coordinates of each point are independently perturbed by normally distributed
small quantities, and investigate the effect of such perturbations on the DT of
the set. We focus on two special configurations, where (1) the points of $P$
form a uniform grid, and (2) the points of $P$ are vertices of a regular
polygon.
We present interesting (and sometimes surprising) empirical findings and
properties of the perturbed DTs for these cases, and give theoretical
explanations to some of them.