-
Article
Spanning Properties of Theta–Theta-6
We show that, unlike the Yao–Yao graph \(YY_6\)YY6, the Theta–Theta graph \({\varTheta }{\varTheta }_6\)ΘΘ6 defined by six cones is a spanner for sets of points in convex position. We also show that, for sets of ...
-
Article
Subquadratic Algorithms for Algebraic 3SUM
The 3SUM problem asks if an input n-set of real numbers contains a triple whose sum is zero. We qualify such a triple of degenerate because the probability of finding one in a random input is zero. We consider th...
-
Article
Incremental Voronoi Diagrams
We study the amortized number of combinatorial changes (edge insertions and removals) needed to update the graph structure of the Voronoi diagram (and several variants thereof) of a set S of n sites in the plane ...
-
Article
Coverage with k-transmitters in the presence of obstacles
For a fixed integer k≥0, a k-transmitter is an omnidirectional wireless transmitter with an infinite broadcast range that is able to penetrate up to k “walls”, represented as line segments in the plane. We develo...
-
Article
Continuous Blooming of Convex Polyhedra
We construct the first two continuous bloomings of all convex polyhedra. First, the source unfolding can be continuously bloomed. Second, any unfolding of a convex polyhedron can be refined (further cut, by a ...
-
Article
Geodesic Ham-Sandwich Cuts
Let P be a simple polygon with m vertices, k of which are reflex, and which contains r red points and b blue points in its interior. Let n = m + r + b. A ham-sandwich geodesic is a shortest path in P between t...
-
Article
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries
Given a set R of red points and a set B of blue points, the nearest-neighbour decision rule classifies a new point q as red (respectively, blue) if the closest point to q in R ⋃ B comes from R (respectively, B...
-
Chapter and Conference Paper
Queaps
We present a new priority queue data structure, the queap, that executes insertion in O(1) amortized time and Extract-min in O(log(k + 2)) amortized time if there are k items that have been in the heap longer tha...
-
Chapter and Conference Paper
Key Independent Optimality
A new form of optimality for comparison based static dictionaries is introduced. This type of optimality, key-independent optimality, is motivated by applications that assign key values randomly. It is shown t...