
We present an efficient dynamic data structure that supports geodesic nearest
neighbor queries for a set $S$ of point sites in a static simple polygon $P$.
Our data structure allows us to insert a new site in $S$, delete a site from
$S$, and ask for the site in $S$ closest to an arbitrary query point $q \in P$.
All distances are measured using the geodesic distance, that is, the length of
the shortest path that is completely contained in $P$. Our data structure
achieves polylogarithmic update and query times, and uses $O(n\log^3n\log m +
m)$ space, where $n$ is the number of sites in $S$ and $m$ is the number of
vertices in $P$. The crucial ingredient in our data structure is an implicit
representation of a vertical shallow cutting of the geodesic distance
functions. We show that such an implicit representation exists, and that we can
compute it efficiently.

The GromovHausdorff (GH) distance is a natural way to measure distance
between two metric spaces. We prove that it is $\mathrm{NP}$hard to
approximate the GromovHausdorff distance better than a factor of $3$ for
geodesic metrics on a pair of trees. We complement this result by providing a
polynomial time $O(\min\{n, \sqrt{rn}\})$approximation algorithm for computing
the GH distance between a pair of metric trees, where $r$ is the ratio of the
longest edge length in both trees to the shortest edge length. For metric trees
with unit length edges, this yields an $O(\sqrt{n})$approximation algorithm.

We study a pathplanning problem amid a set $\mathcal{O}$ of obstacles in
$\mathbb{R}^2$, in which we wish to compute a short path between two points
while also maintaining a high clearance from $\mathcal{O}$; the clearance of a
point is its distance from a nearest obstacle in $\mathcal{O}$. Specifically,
the problem asks for a path minimizing the reciprocal of the clearance
integrated over the length of the path. We present the first polynomialtime
approximation scheme for this problem. Let $n$ be the total number of obstacle
vertices and let $\varepsilon \in (0,1]$. Our algorithm computes in time
$O(\frac{n^2}{\varepsilon ^2} \log \frac{n}{\varepsilon})$ a path of total cost
at most $(1+\varepsilon)$ times the cost of the optimal path.

A regret minimizing set Q is a small size representation of a much larger
database P so that user queries executed on Q return answers whose scores are
not much worse than those on the full dataset. In particular, a kregret
minimizing set has the property that the regret ratio between the score of the
top1 item in Q and the score of the topk item in P is minimized, where the
score of an item is the inner product of the item's attributes with a user's
weight (preference) vector. The problem is challenging because we want to find
a single representative set Q whose regret ratio is small with respect to all
possible user weight vectors.
We show that kregret minimization is NPComplete for all dimensions d >= 3.
This settles an open problem from Chester et al. [VLDB 2014], and resolves the
complexity status of the problem for all d: the problem is known to have
polynomialtime solution for d <= 2. In addition, we propose two new
approximation schemes for regret minimization, both with provable guarantees,
one based on coresets and another based on hitting sets. We also carry out
extensive experimental evaluation, and show that our schemes compute
regretminimizing sets comparable in size to the greedy algorithm proposed in
[VLDB 14] but our schemes are significantly faster and scalable to large data
sets.

Nearestneighbor search, which returns the nearest neighbor of a query point
in a set of points, is an important and widely studied problem in many fields,
and it has wide range of applications. In many of them, such as sensor
databases, locationbased services, face recognition, and mobile data, the
location of data is imprecise. We therefore study nearestneighbor queries in a
probabilistic framework in which the location of each input point is specified
as a probability distribution function. We present efficient algorithms for
 computing all points that are nearest neighbors of a query point with
nonzero probability; and
 estimating the probability of a point being the nearest neighbor of a query
point, either exactly or within a specified additive error.

We give the first subquadratictime approximation schemes for dynamic time
warping (DTW) and edit distance (ED) of several natural families of point
sequences in $\mathbb{R}^d$, for any fixed $d \ge 1$. In particular, our
algorithms compute $(1+\varepsilon)$approximations of DTW and ED in time
nearlinear for point sequences drawn from kpacked or kbounded curves, and
subquadratic for backbone sequences. Roughly speaking, a curve is
$\kappa$packed if the length of its intersection with any ball of radius $r$
is at most $\kappa \cdot r$, and a curve is $\kappa$bounded if the subcurve
between two curve points does not go too far from the two points compared to
the distance between the two points. In backbone sequences, consecutive points
are spaced at approximately equal distances apart, and no two points lie very
close together. Recent results suggest that a subquadratic algorithm for DTW or
ED is unlikely for an arbitrary pair of point sequences even for $d=1$. Our
algorithms work by constructing a small set of rectangular regions that cover
the entries of the dynamic programming table commonly used for these distance
measures. The weights of entries inside each rectangle are roughly the same, so
we are able to use efficient procedures to approximately compute the cheapest
paths through these rectangles.

Let $P$ be a set of $n$ points in $\mathrm{R}^2$, and let $\mathrm{DT}(P)$
denote its Euclidean Delaunay triangulation. We introduce the notion of an edge
of $\mathrm{DT}(P)$ being {\it stable}. Defined in terms of a parameter
$\alpha>0$, a Delaunay edge $pq$ is called $\alpha$stable, if the (equal)
angles at which $p$ and $q$ see the corresponding Voronoi edge $e_{pq}$ are at
least $\alpha$. A subgraph $G$ of $\mathrm{DT}(P)$ is called {\it $(c\alpha,
\alpha)$stable Delaunay graph} ($\mathrm{SDG}$ in short), for some constant $c
\ge 1$, if every edge in $G$ is $\alpha$stable and every $c\alpha$stable of
$\mathrm{DT}(P)$ is in $G$.
We show that if an edge is stable in the Euclidean Delaunay triangulation of
$P$, then it is also a stable edge, though for a different value of $\alpha$,
in the Delaunay triangulation of $P$ under any convex distance function that is
sufficiently close to the Euclidean norm, and viceversa. In particular, a
$6\alpha$stable edge in $\mathrm{DT}(P)$ is $\alpha$stable in the Delaunay
triangulation under the distance function induced by a regular $k$gon for $k
\ge 2\pi/\alpha$, and viceversa. Exploiting this relationship and the analysis
in~\cite{polydel}, we present a linearsize kinetic data structure (KDS) for
maintaining an $(8\alpha,\alpha)$$\mathrm{SDG}$ as the points of $P$ move. If
the points move along algebraic trajectories of bounded degree, the KDS
processes nearly quadratic events during the motion, each of which can
processed in $O(\log n)$ time. Finally, we show that a number of useful
properties of $\mathrm{DT}(P)$ are retained by $\mathrm{SDG}$ of $P$.

We study the convexhull problem in a probabilistic setting, motivated by the
need to handle data uncertainty inherent in many applications, including sensor
databases, locationbased services and computer vision. In our framework, the
uncertainty of each input site is described by a probability distribution over
a finite number of possible locations including a \emph{null} location to
account for nonexistence of the point. Our results include both exact and
approximation algorithms for computing the probability of a query point lying
inside the convex hull of the input, timespace tradeoffs for the membership
queries, a connection between Tukey depth and membership queries, as well as a
new notion of $\some$hull that may be a useful representation of uncertain
hulls.

We consider maintaining the contour tree $\mathbb{T}$ of a piecewiselinear
triangulation $\mathbb{M}$ that is the graph of a time varying height function
$h: \mathbb{R}^2 \rightarrow \mathbb{R}$. We carefully describe the
combinatorial change in $\mathbb{T}$ that happen as $h$ varies over time and
how these changes relate to topological changes in $\mathbb{M}$. We present a
kinetic data structure that maintains the contour tree of $h$ over time. Our
data structure maintains certificates that fail only when $h(v)=h(u)$ for two
adjacent vertices $v$ and $u$ in $\mathbb{M}$, or when two saddle vertices lie
on the same contour of $\mathbb{M}$. A certificate failure is handled in
$O(\log(n))$ time. We also show how our data structure can be extended to
handle a set of general update operations on $\mathbb{M}$ and how it can be
applied to maintain topological persistence pairs of time varying functions.

Let $P$ be a set of $n$ points and $Q$ a convex $k$gon in ${\mathbb R}^2$.
We analyze in detail the topological (or discrete) changes in the structure of
the Voronoi diagram and the Delaunay triangulation of $P$, under the convex
distance function defined by $Q$, as the points of $P$ move along prespecified
continuous trajectories. Assuming that each point of $P$ moves along an
algebraic trajectory of bounded degree, we establish an upper bound of
$O(k^4n\lambda_r(n))$ on the number of topological changes experienced by the
diagrams throughout the motion; here $\lambda_r(n)$ is the maximum length of an
$(n,r)$DavenportSchinzel sequence, and $r$ is a constant depending on the
algebraic degree of the motion of the points. Finally, we describe an algorithm
for efficiently maintaining the above structures, using the kinetic data
structure (KDS) framework.

Let $P$ be a set of $n$ points in $\R^d$. We present a linearsize data
structure for answering range queries on $P$ with constantcomplexity
semialgebraic sets as ranges, in time close to $O(n^{11/d})$. It essentially
matches the performance of similar structures for simplex range searching, and,
for $d\ge 5$, significantly improves earlier solutions by the first two authors
obtained in~1994. This almost settles a longstanding open problem in range
searching.
The data structure is based on the polynomialpartitioning technique of Guth
and Katz [arXiv:1011.4105], which shows that for a parameter $r$, $1 < r \le
n$, there exists a $d$variate polynomial $f$ of degree $O(r^{1/d})$ such that
each connected component of $\R^d\setminus Z(f)$ contains at most $n/r$ points
of $P$, where $Z(f)$ is the zero set of $f$. We present an efficient randomized
algorithm for computing such a polynomial partition, which is of independent
interest and is likely to have additional applications.

With recent advances in sensing and tracking technology, trajectory data is
becoming increasingly pervasive and analysis of trajectory data is becoming
exceedingly important. A fundamental problem in analyzing trajectory data is
that of identifying common patterns between pairs or among groups of
trajectories. In this paper, we consider the problem of identifying similar
portions between a pair of trajectories, each observed as a sequence of points
sampled from it.
We present new measures of trajectory similarity  both local and global
 between a pair of trajectories to distinguish between similar and
dissimilar portions. Our model is robust under noise and outliers, it does not
make any assumptions on the sampling rates on either trajectory, and it works
even if they are partially observed. Additionally, the model also yields a
scalar similarity score which can be used to rank multiple pairs of
trajectories according to similarity, e.g. in clustering applications. We also
present efficient algorithms for computing the similarity under our measures;
the worstcase running time is quadratic in the number of sample points.
Finally, we present an extensive experimental study evaluating the
effectiveness of our approach on real datasets, comparing with it with earlier
approaches, and illustrating many issues that arise in trajectory data. Our
experiments show that our approach is highly accurate in distinguishing similar
and dissimilar portions as compared to earlier methods even with sparse
sampling.

We present Roadmap Sparsification by Edge Contraction (RSEC), a simple and
effective algorithm for reducing the size of a motionplanning roadmap. The
algorithm exhibits minimal effect on the quality of paths that can be extracted
from the new roadmap. The primitive operation used by RSEC is edge contraction
 the contraction of a roadmap edge to a single vertex and the connection of
the new vertex to the neighboring vertices of the contracted edge. For certain
scenarios, we compress more than 98% of the edges and vertices at the cost of
degradation of average shortest path length by at most 2%.

The Fr\'echet distance is a similarity measure between two curves $A$ and
$B$: Informally, it is the minimum length of a leash required to connect a dog,
constrained to be on $A$, and its owner, constrained to be on $B$, as they walk
without backtracking along their respective curves from one endpoint to the
other. The advantage of this measure on other measures such as the Hausdorff
distance is that it takes into account the ordering of the points along the
curves.
The discrete Fr\'echet distance replaces the dog and its owner by a pair of
frogs that can only reside on $n$ and $m$ specific pebbles on the curves $A$
and $B$, respectively. These frogs hop from a pebble to the next without
backtracking. The discrete Fr\'echet distance can be computed by a rather
straightforward quadratic dynamic programming algorithm. However, despite a
considerable amount of work on this problem and its variations, there is no
subquadratic algorithm known, even for approximation versions of the problem.
In this paper we present a subquadratic algorithm for computing the discrete
Fr\'echet distance between two sequences of points in the plane, of respective
lengths $m\le n$. The algorithm runs in $O(\dfrac{mn\log\log n}{\log n})$ time
and uses $O(n+m)$ storage. Our approach uses the geometry of the problem in a
subtle way to encode legal positions of the frogs as states of a finite
automata.

We consider the problem of maintaining the Euclidean Delaunay triangulation
$\DT$ of a set $P$ of $n$ moving points in the plane, along algebraic
trajectories of constant description complexity. Since the best known upper
bound on the number of topological changes in the full $\DT$ is nearly cubic,
we seek to maintain a suitable portion of it that is less volatile yet retains
many useful properties. We introduce the notion of a stable Delaunay graph,
which is a dynamic subgraph of the Delaunay triangulation. The stable Delaunay
graph (a) is easy to define, (b) experiences only a nearly quadratic number of
discrete changes, (c) is robust under small changes of the norm, and (d)
possesses certain useful properties.
The stable Delaunay graph ($\SDG$ in short) is defined in terms of a
parameter $\alpha>0$, and consists of Delaunay edges $pq$ for which the angles
at which $p$ and $q$ see their Voronoi edge $e_{pq}$ are at least $\alpha$. We
show that (i) $\SDG$ always contains at least roughly one third of the Delaunay
edges; (ii) it contains the $\beta$skeleton of $P$, for
$\beta=1+\Omega(\alpha^2)$; (iii) it is stable, in the sense that its edges
survive for long periods of time, as long as the orientations of the segments
connecting (nearby) points of $P$ do not change by much; and (iv) stable
Delaunay edges remain stable (with an appropriate redefinition of stability) if
we replace the Euclidean norm by any sufficiently close norm.
In particular, we can approximate the Euclidean norm by a polygonal norm
(namely, a regular $k$gon, with $k=\Theta(1/\alpha)$), and keep track of a
Euclidean $\SDG$ by maintaining the full Delaunay triangulation of $P$ under
the polygonal norm.
We describe two kinetic data structures for maintaining $\SDG$. Both
structures use $O^*(n)$ storage and process $O^*(n^2)$ events during the
motion, each in $O^*(1)$ time.

Let P be a set of n points in R^3. The 2center problem for P is to find two
congruent balls of minimum radius whose union covers P. We present two
randomized algorithms for computing a 2center of P. The first algorithm runs
in O(n^3 log^5 n) expected time, and the second algorithm runs in O((n^2 log^5
n) /(1r*/r_0)^3) expected time, where r* is the radius of the 2center balls
of P and r_0 is the radius of the smallest enclosing ball of P. The second
algorithm is faster than the first one as long as r* is not too close to r_0,
which is equivalent to the condition that the centers of the two covering balls
be not too close to each other.

Given a set P of n points in R^d, an epskernel K subset P approximates the
directional width of P in every direction within a relative (1eps) factor. In
this paper we study the stability of epskernels under dynamic insertion and
deletion of points to P and by changing the approximation factor eps. In the
first case, we say an algorithm for dynamically maintaining a epskernel is
stable if at most O(1) points change in K as one point is inserted or deleted
from P. We describe an algorithm to maintain an epskernel of size
O(1/eps^{(d1)/2}) in O(1/eps^{(d1)/2} + log n) time per update. Not only does
our algorithm maintain a stable epskernel, its update time is faster than any
known algorithm that maintains an epskernel of size O(1/eps^{(d1)/2}). Next,
we show that if there is an epskernel of P of size k, which may be
dramatically less than O(1/eps^{(d1)/2}), then there is an (eps/2)kernel of P
of size O(min {1/eps^{(d1)/2}, k^{floor(d/2)} log^{d2} (1/eps)}). Moreover,
there exists a point set P in R^d and a parameter eps > 0 such that if every
epskernel of P has size at least k, then any (eps/2)kernel of P has size
Omega(k^{floor(d/2)}).

Multichannel wireless networks are increasingly being employed as
infrastructure networks, e.g. in metro areas. Nodes in these networks
frequently employ directional antennas to improve spatial throughput. In such
networks, given a source and destination, it is of interest to compute an
optimal path and channel assignment on every link in the path such that the
path bandwidth is the same as that of the link bandwidth and such a path
satisfies the constraint that no two consecutive links on the path are assigned
the same channel, referred to as "Channel Discontinuity Constraint" (CDC).
CDCpaths are also quite useful for TDMA system, where preferably every
consecutive links along a path are assigned different time slots.
This paper contains several contributions. We first present an $O(N^{2})$
distributed algorithm for discovering the shortest CDCpath between given
source and destination. This improves the running time of the $O(N^{3})$
centralized algorithm of Ahuja et al. for finding the minimumweight CDCpath.
Our second result is a generalized $t$spanner for CDCpath; For any $\theta>0$
we show how to construct a subnetwork containing only $O(\frac{N}{\theta})$
edges, such that that length of shortest CDCpaths between arbitrary sources
and destinations increases by only a factor of at most
$(12\sin{\tfrac{\theta}{2}})^{2}$. We propose a novel algorithm to compute
the spanner in a distributed manner using only $O(n\log{n})$ messages. An
important conclusion of this scheme is in the case of directional antennas are
used. In this case, it is enough to consider only the two closest nodes in each
cone.

We describe algorithms for finding the regression of t, a sequence of values,
to the closest sequence s by mean squared error, so that s is always increasing
(isotonicity) and so the values of two consecutive points do not increase by
too much (Lipschitz). The isotonicity constraint can be replaced with a
unimodular constraint, where there is exactly one local maximum in s. These
algorithm are generalized from sequences of values to trees of values. For each
scenario we describe nearlinear time algorithms.

For a set P of n points in R^2, the Euclidean 2center problem computes a
pair of congruent disks of the minimal radius that cover P. We extend this to
the (2,k)center problem where we compute the minimal radius pair of congruent
disks to cover nk points of P. We present a randomized algorithm with O(n k^7
log^3 n) expected running time for the (2,k)center problem. We also study the
(p,k)center problem in R}^2 under the \ell_\inftymetric. We give solutions
for p=4 in O(k^{O(1)} n log n) time and for p=5 in O(k^{O(1)} n log^5 n) time.

Here we present the results of the NSFfunded Workshop on Computational
Topology, which met on June 11 and 12 in Miami Beach, Florida. This report
identifies important problems involving both computation and topology.

Problems presented at the openproblem session of the 14th Annual ACM
Symposium on Computational Geometry are listed.