-
Chapter and Conference Paper
Fault-Tolerant Spanners in Networks with Symmetric Directional Antennas
Let P be a set of points in the plane, each equipped with a directional antenna that can cover a sector of angle \(\alpha \) ...
-
Chapter and Conference Paper
Computing the Smallest Color-Spanning Axis-Parallel Square
For a given set of n colored points with k colors in the plane, we study the problem of computing the smallest color-spanning axis-parallel square. First, for a dynamic set of colored points on the real line, we ...
-
Chapter and Conference Paper
Kinetic Pie Delaunay Graph and Its Applications
We construct a new proximity graph, called the Pie Delaunay graph, on a set of n points which is a super graph of Yao graph and Euclidean minimum spanning tree (EMST). We efficiently maintain the Pi...
-
Chapter and Conference Paper
Piecewise-Linear Approximations of Uncertain Functions
We study the problem of approximating a function F: ℝ → ℝ by a piecewise-linear function \(\overline{\mathrm{F}}\) when the values of F at ...
-
Chapter and Conference Paper
Geometric Spanners for Weighted Point Sets
Let (S,d) be a finite metric space, where each element p ∈ S has a non-negative weight w(p). We study spanners for the set S with respect to weighted distance function d w ...
-
Chapter and Conference Paper
On the Power of the Semi-Separated Pair Decomposition
A Semi-Separated Pair Decomposition (SSPD), with parameter s > 1, of a set \(S\subset {\mathbb R}^d\) is a set {(A ...
-
Chapter and Conference Paper
Out-of-Order Event Processing in Kinetic Data Structures
We study the problem of designing kinetic data structures (KDS’s for short) when event times cannot be computed exactly and events may be processed in a wrong order. In traditional KDS’s this can lead to major...