
The pairing heap is a classical heap data structure introduced in 1986 by
Fredman, Sedgewick, Sleator, and Tarjan. It is remarkable both for its
simplicity and for its excellent performance in practice. The "magic" of
pairing heaps lies in the restructuring that happens after the deletion of the
smallest item. The resulting collection of trees is consolidated in two rounds:
a lefttoright pairing round, followed by a righttoleft accumulation round.
Fredman et al. showed, via an elegant correspondence to splay trees, that in a
pairing heap of size $n$ all operations take $O(\log{n})$ amortized time. They
also proposed an arguably more natural variant, where both pairing and
accumulation are performed in a combined lefttoright round (called the
forward variant of pairing heaps). The analogy to splaying breaks down in this
case, and the analysis of the forward variant was left open.
In this paper we show that inserting an item and deleting the minimum in a
forwardvariant pairing heap both take amortized time $O(\log{n} \cdot
4^{\sqrt{\log{n}}} )$. This is the first improvement over the $O(\sqrt{n})$
bound showed by Fredman et al. three decades ago. Our analysis relies on a new
potential function that tracks parentchild rankdifferences in the heap.

Let $P \subset \mathbb{R}^2$ be a planar $n$point set such that each point
$p \in P$ has an associated radius $r_p > 0$. The transmission graph $G$ for
$P$ is the directed graph with vertex set $P$ such that for any $p, q \in P$,
there is an edge from $p$ to $q$ if and only if $d(p, q) \leq r_p$.
Let $t > 1$ be a constant. A $t$spanner for $G$ is a subgraph $H \subseteq
G$ with vertex set $P$ so that for any two vertices $p,q \in P$, we have
$d_H(p, q) \leq t d_G(p, q)$, where $d_H$ and $d_G$ denote the shortest path
distance in $H$ and $G$, respectively (with Euclidean edge lengths). We show
how to compute a $t$spanner for $G$ with $O(n)$ edges in $O(n (\log n + \log
\Psi))$ time, where $\Psi$ is the ratio of the largest and smallest radius of a
point in $P$. Using more advanced data structures, we obtain a construction
that runs in $O(n \log^5 n)$ time, independent of $\Psi$.
We give two applications for our spanners. First, we show how to use our
spanner to find a BFS tree in $G$ from any given start vertex in $O(n \log n)$
time (in addition to the time it takes to build the spanner). Second, we show
how to use our spanner to extend a reachability oracle to answer geometric
reachability queries. In a geometric reachability query we ask whether a vertex
$p$ in $G$ can "reach" a target $q$ which is an arbitrary point in the plane
(rather than restricted to be another vertex $q$ of $G$ in a standard
reachability query). Our spanner allows the reachability oracle to answer
geometric reachability queries with an additive overhead of $O(\log n\log
\Psi)$ to the query time and $O(n \log \Psi)$ to the space.

We design new differentially private algorithms for the Euclidean kmeans
problem, both in the centralized model and in the local model of differential
privacy. In both models, our algorithms achieve significantly improved error
rates over the previous stateoftheart. In addition, in the local model, our
algorithm significantly reduces the number of needed interactions.
Although the problem has been widely studied in the context of differential
privacy, all of the existing constructions achieve only super constant
approximation factors. We present, for the first time, efficient private
algorithms for the problem with constant multiplicative error.

In this work, we provide theoretical guarantees for reward decomposition in
deterministic MDPs. Reward decomposition is a special case of Hierarchical
Reinforcement Learning, that allows one to learn many policies in parallel and
combine them into a composite solution. Our approach builds on mapping this
problem into a Reward Discounted Traveling Salesman Problem, and then deriving
approximate solutions for it. In particular, we focus on approximate solutions
that are local, i.e., solutions that only observe information about the current
state. Local policies are easy to implement and do not require substantial
computational resources as they do not perform planning. While local
deterministic policies, like Nearest Neighbor, are being used in practice for
hierarchical reinforcement learning, we propose three stochastic policies that
guarantee better performance than any deterministic policy.

In 1999, Brodal and Fagerberg (BF) gave an algorithm for maintaining a low
outdegree orientation of a dynamic uniformly sparse graph. Specifically, for a
dynamic graph on $n$vertices, with arboricity bounded by $\alpha$ at all
times, the BF algorithm supports edge updates in $O(\log n)$ amortized update
time, while keeping the maximum outdegree in the graph bounded by $O(\alpha)$.
Such an orientation provides a basic data structure for uniformly sparse
graphs, which found applications to a plethora of dynamic graph algorithms.
A significant weakness of the BF algorithm is the possible \emph{temporary}
blowup of the maximum outdegree, following edge insertions. Although BF
eventually reduces all outdegrees to $O(\alpha)$, local memory usage at the
vertices, which is an important quality measure in distributed systems, cannot
be bounded. We show how to modify the BF algorithm to guarantee that the
outdegrees of all vertices are bounded by $O(\alpha)$ at all times, without
hurting any of its other properties, and present an efficient distributed
implementation of the modified algorithm. This provides the \emph{first}
representation of distributed networks in which the local memory usage at all
vertices is bounded by the arboricity (which is essentially the average degree
of the densest subgraph) rather than the maximum degree.
For settings where there are no local memory constraints, we take the
temporary outdegree blowup to the extreme and allow a permanent outdegree
blowup. This allows us to address the second significant weakness of the BF
algorithm  its inherently \emph{global} nature: An insertion of an edge
$(u,v)$ may trigger changes in the orientations of edges that are far away from
$u$ and $v$. We suggest an alternative \emph{local} scheme, which does not
guarantee any outdegree bound on the vertices, yet is just as efficient as the
BF scheme for various applications.

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 use soft heaps to obtain simpler optimal algorithms for selecting the
$k$th smallest item, and the set of~$k$ smallest items, from a heapordered
tree, from a collection of sorted lists, and from $X+Y$, where $X$ and $Y$ are
two unsorted sets. Our results match, and in some ways extend and improve,
classical results of Frederickson (1993) and Frederickson and Johnson (1982).
In particular, for selecting the $k$th smallest item, or the set of~$k$
smallest items, from a collection of~$m$ sorted lists we obtain a new optimal
"outputsensitive" algorithm that performs only $O(m+\sum_{i=1}^m \log(k_i+1))$
comparisons, where $k_i$ is the number of items of the $i$th list that belong
to the overall set of~$k$ smallest items.

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.

Clustering is a fundamental technique in data analysis. Consider data points
$X$ that lie in a (relaxed) metric space (where the triangle inequality can be
relaxed by a constant factor). Each set of points $Q$ ({\em centers}) defines a
clustering of $X$ according to the closest center with {\em cost}
$V(Q)=\sum_{x\in X} d_{xQ}$. This formulation generalizes classic $k$means
clustering, which uses squared distances. Two basic tasks, parametrized by $k
\geq 1$, are {\em cost estimation}, which returns (approximate) $V(Q)$ for
queries $Q$ such that $Q=k$ and {\em clustering}, which returns an
(approximate) minimizer of $V(Q)$ of size $Q=k$. With very large data sets
$X$, we seek efficient constructions of small summaries that allow us to
efficiently approximate clustering costs over the full data.
We present a novel data reduction tool based on multiobjective
probabilityproportionaltosize (pps) sampling: Our {\em one2all} construction
inputs any set of centers $M$ and efficiently computes a sample of size
$O(M)$ from which we can tightly estimate the clustering cost $V(Q)$ for {\em
any} $Q$ that has at least a fraction of the clustering cost of $M$. For cost
queries, we apply one2all to a bicriteria approximation to obtain a sample of
size $O(k\epsilon^{2})$ for all $Q=k$. For clustering, we propose a wrapper
that applies a blackbox algorithm to a sample and tests clustering quality
over $X$, adaptively increasing the sample size. Our approach exploits the
structure of the data to provide quality guarantees through small samples,
without the use of typically much larger worstcasesize summaries.

Let $S \subset \mathbb{R}^2$ be a set of $n$ sites. The unit disk graph
$\text{UD}(S)$ on $S$ has vertex set $S$ and an edge between two distinct sites
$s,t \in S$ if and only if $s$ and $t$ have Euclidean distance $st \leq 1$.
A routing scheme $R$ for $\text{UD}(S)$ assigns to each site $s \in S$ a
label $\ell(s)$ and a routing table $\rho(s)$. For any two sites $s, t \in S$,
the scheme $R$ must be able to route a packet from $s$ to $t$ in the following
way: given a current site $r$ (initially, $r = s$), a header $h$ (initially
empty), and the label $\ell(t)$ of the target, the scheme $R$ consults the
routing table $\rho(r)$ to compute a neighbor $r'$ of $r$, a new header $h'$,
and the label $\ell(t')$ of an intermediate target $t'$. (The label of the
original target may be stored at the header $h'$.) The packet is then routed to
$r'$, and the procedure is repeated until the packet reaches $t$. The resulting
sequence of sites is called the routing path. The stretch of $R$ is the maximum
ratio of the (Euclidean) length of the routing path produced by $R$ and the
shortest path in $\text{UD}(S)$, over all pairs of distinct sites in $S$.
For any given $\varepsilon > 0$, we show how to construct a routing scheme
for $\text{UD}(S)$ with stretch $1+\varepsilon$ using labels of $O(\log n)$
bits and routing tables of $O(\varepsilon^{5}\log^2 n \log^2 D)$ bits, where
$D$ is the (Euclidean) diameter of $\text{UD}(S)$. The header size is $O(\log n
\log D)$ bits.

We consider the problem of online Mincost Perfect Matching with Delays
(MPMD) recently introduced by Emek et al, (STOC 2016). This problem is defined
on an underlying $n$point metric space. An adversary presents realtime
requests online at points of the metric space, and the algorithm is required to
match them, possibly after keeping them waiting for some time. The cost
incurred is the sum of the distances between matched pairs of points (the
connection cost), and the sum of the waiting times of the requests (the delay
cost). We present an algorithm with a competitive ratio of $O(\log n)$, which
improves the upper bound of $O(\log^2n+\log\Delta)$ of Emek et al, by removing
the dependence on $\Delta$, the aspect ratio of the metric space (which can be
unbounded as a function of $n$). The core of our algorithm is a deterministic
algorithm for MPMD on metrics induced by edgeweighted trees of height $h$,
whose cost is guaranteed to be at most $O(1)$ times the connection cost plus
$O(h)$ times the delay cost of every feasible solution. The reduction from MPMD
on arbitrary metrics to MPMD on trees is achieved using the result on embedding
$n$point metric spaces into distributions over weighted hierarchically
separated trees of height $O(\log n)$, with distortion $O(\log n)$. We also
prove a lower bound of $\Omega(\sqrt{\log n})$ on the competitive ratio of any
randomized algorithm. This is the first lower bound which increases with $n$,
and is attained on the metric of $n$ equally spaced points on a line.
The problem of Mincost Bipartite Perfect Matching with Delays (MBPMD) is the
same as MPMD except that every request is either positive or negative, and
requests can be matched only if they have opposite polarity. We prove an upper
bound of $O(\log n)$ and a lower bound of $\Omega(\log^{1/3}n)$ on the
competitive ratio of MBPMD with a more involved analysis.

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.

$\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 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.

Let $P \subset \mathbb{R}^d$ be a set of $n$ points in $d$ dimensions such
that each point $p \in P$ has an associated radius $r_p > 0$. The transmission
graph $G$ for $P$ is the directed graph with vertex set $P$ such that there is
an edge from $p$ to $q$ if and only if $pq \leq r_p$, for any $p, q \in P$.
A reachability oracle is a data structure that decides for any two vertices
$p, q \in G$ whether $G$ has a path from $p$ to $q$. The quality of the oracle
is measured by the space requirement $S(n)$, the query time $Q(n)$, and the
preprocessing time. For transmission graphs of onedimensional point sets, we
can construct in $O(n \log n)$ time an oracle with $Q(n) = O(1)$ and $S(n) =
O(n)$. For planar point sets, the ratio $\Psi$ between the largest and the
smallest associated radius turns out to be an important parameter. We present
three data structures whose quality depends on $\Psi$: the first works only for
$\Psi < \sqrt{3}$ and achieves $Q(n) = O(1)$ with $S(n) = O(n)$ and
preprocessing time $O(n\log n)$; the second data structure gives $Q(n) =
O(\Psi^3 \sqrt{n})$ and $S(n) = O(\Psi^3 n^{3/2})$; the third data structure is
randomized with $Q(n) = O(n^{2/3}\log^{1/3} \Psi \log^{2/3} n)$ and $S(n) =
O(n^{5/3}\log^{1/3} \Psi \log^{2/3} n)$ and answers queries correctly with high
probability.

We introduce the hollow heap, a very simple data structure with the same
amortized efficiency as the classical Fibonacci heap. All heap operations
except delete and deletemin take $O(1)$ time, worst case as well as amortized;
delete and deletemin take $O(\log n)$ amortized time on a heap of $n$ items.
Hollow heaps are by far the simplest structure to achieve this. Hollow heaps
combine two novel ideas: the use of lazy deletion and reinsertion to do
decreasekey operations, and the use of a dag (directed acyclic graph) instead
of a tree or set of trees to represent a heap. Lazy deletion produces hollow
nodes (nodes without items), giving the data structure its name.

We consider a generalization of the secretary problem where contracts are
temporary, and for a fixed duration. This models online hiring of temporary
employees, or online auctions for reusable resources. The problem is related
to the question of Finding a large independent set in a random unit interval
graph.

The average distance from a node to all other nodes in a graph, or from a
query point in a metric space to a set of points, is a fundamental quantity in
data analysis. The inverse of the average distance, known as the (classic)
closeness centrality of a node, is a popular importance measure in the study of
social networks. We develop novel structural insights on the sparsifiability of
the distance relation via weighted sampling. Based on that, we present highly
practical algorithms with strong statistical guarantees for fundamental
problems. We show that the average distance (and hence the centrality) for all
nodes in a graph can be estimated using $O(\epsilon^{2})$ singlesource
distance computations. For a set $V$ of $n$ points in a metric space, we show
that after preprocessing which uses $O(n)$ distance computations we can compute
a weighted sample $S\subset V$ of size $O(\epsilon^{2})$ such that the average
distance from any query point $v$ to $V$ can be estimated from the distances
from $v$ to $S$. Finally, we show that for a set of points $V$ in a metric
space, we can estimate the average pairwise distance using $O(n+\epsilon^{2})$
distance computations. The estimate is based on a weighted sample of
$O(\epsilon^{2})$ pairs of points, which is computed using $O(n)$ distance
computations. Our estimates are unbiased with normalized mean square error
(NRMSE) of at most $\epsilon$. Increasing the sample size by a $O(\log n)$
factor ensures that the probability that the relative error exceeds $\epsilon$
is polynomially small.

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$.

The discrete Fr\'echet distance is a useful similarity measure for comparing
two sequences of points $P=(p_1,\ldots, p_m)$ and $Q=(q_1,\ldots,q_n)$. In many
applications, the quality of the matching can be improved if we let $Q$ undergo
some transformation relative to $P$. In this paper we consider the problem of
finding a translation of $Q$ that brings the discrete Fr\'echet distance
between $P$ and $Q$ to a minimum. We devise an algorithm that computes the
minimum discrete Fr\'echet distance under translation in $\mathbb{R}^2$, and
runs in $O(m^3n^2(1+\log(n/m))\log(m+n))$ time, assuming $m\leq n$. This
improves a previous algorithm of Jiang et al.~\cite{JXZ08}, which runs in
$O(m^3n^3 \log(m + n))$ time.

Hub Labeling (HL) is a data structure for distance oracles. Hierarchical HL
(HHL) is a special type of HL, that received a lot of attention from a
practical point of view. However, theoretical questions such as NPhardness and
approximation guarantee for HHL algorithms have been left aside. In this paper
we study HL and HHL from the complexity theory point of view. We prove that
both HL and HHL are NPhard, and present upper and lower bounds for the
approximation ratios of greedy HHL algorithms used in practice. We also
introduce a new variant of the greedy HHL algorithm and a proof that it
produces small labels for graphs with small highway dimension.

Given a set $P$ of $n$ points in $\mathbb{R}^3$, we show that, for any
$\varepsilon >0$, there exists an $\varepsilon$net of $P$ for halfspace
ranges, of size $O(1/\varepsilon)$. We give five proofs of this result, which
are arguably simpler than previous proofs \cite{mswhnlls90, cviaags07,
prnepen08}. We also consider several related variants of this result,
including the case of points and pseudodisks in the plane.

The Fibonacci heap is a classic data structure that supports deletions in
logarithmic amortized time and all other heap operations in O(1) amortized
time. We explore the design space of this data structure. We propose a version
with the following improvements over the original: (i) Each heap is represented
by a single heapordered tree, instead of a set of trees. (ii) Each
decreasekey operation does only one cut and a cascade of rank changes, instead
of doing a cascade of cuts. (iii) The outcomes of all comparisons done by the
algorithm are explicitly represented in the data structure, so none are wasted.
We also give an example to show that without cascading cuts or rank changes,
both the original data structure and the new version fail to have the desired
efficiency, solving an open problem of Fredman. Finally, we illustrate the
richness of the design space by proposing several alternative ways to do
cascading rank changes, including a randomized strategy related to one
previously proposed by Karger. We leave the analysis of these alternatives as
intriguing open problems.

Most discovery systems for silent failures work in two phases: a continuous
monitoring phase that detects presence of failures through probe packets and a
localization phase that pinpoints the faulty element(s). This separation is
important because localization requires significantly more resources than
detection and should be initiated only when a fault is present.
We focus on improving the efficiency of the detection phase, where the goal
is to balance the overhead with the cost associated with longer failure
detection times. We formulate a general model which unifies the treatment of
probe scheduling mechanisms, stochastic or deterministic, and different cost
objectives  minimizing average detection time (SUM) or worstcase detection
time (MAX).
We then focus on two classes of schedules. {\em Memoryless schedules}  a
subclass of stochastic schedules which is simple and suitable for distributed
deployment. We show that the optimal memorlyess schedulers can be efficiently
computed by convex programs (for SUM objectives) or linear programs (for MAX
objectives), and surprisingly perhaps, are guaranteed to have expected
detection times that are not too far off the (NP hard) stochastic optima. {\em
Deterministic schedules} allow us to bound the maximum (rather than expected)
cost of undetected faults, but like stochastic schedules, are NP hard to
optimize. We develop novel efficient deterministic schedulers with provable
approximation ratios.
An extensive simulation study on real networks, demonstrates significant
performance gains of our memoryless and deterministic schedulers over previous
approaches. Our unified treatment also facilitates a clear comparison between
different objectives and scheduling mechanisms.

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.