
Dynamic Connectivity in Disk Graphs
Let S be a set of n sites, each associated with a point in ℝ^2 and a rad...
read it

Long plane trees
Let 𝒫 be a finite set of points in the plane in general position. For an...
read it

Minimum Cuts in Geometric Intersection Graphs
Let 𝒟 be a set of n disks in the plane. The disk graph G_𝒟 for 𝒟 is the ...
read it

A Simple Randomized O(n log n)–Time ClosestPair Algorithm in Doubling Metrics
Consider a metric space (P,dist) with N points whose doubling dimension ...
read it

Long Alternating Paths Exist
Let P be a set of 2n points in convex position, such that n points are c...
read it

Computational Complexity of the αHamSandwich Problem
The classic HamSandwich theorem states that for any d measurable sets i...
read it

Routing in Unit Disk Graphs without Dynamic Headers
Let V⊂ℝ^2 be a set of n sites in the plane. The unit disk graph DG(V) of...
read it

The Tree Stabbing Number is not Monotone
Let P ⊆ℝ^2 be a set of points and T be a spanning tree of P. The stabbin...
read it

Maximum Matchings in Geometric Intersection Graphs
Let G be an intersection graph of n geometric objects in the plane. We s...
read it

Minimal Representations of Order Types by Geometric Graphs
In order to have a compact visualization of the order type of a given po...
read it

Nodimensional Tverberg Theorems and Algorithms
Tverberg's theorem is a classic result in discrete geometry. It states t...
read it

Triangles and Girth in Disk Graphs and Transmission Graphs
Let S ⊂R^2 be a set of n sites, where each s ∈ S has an associated radiu...
read it

On the Stretch Factor of Polygonal Chains
Let P=(p_1, p_2, ..., p_n) be a polygonal chain. The stretch factor of P...
read it

A Constructive Proof of a Concentration Bound for RealValued Random Variables
Almost 10 years ago, Impagliazzo and Kabanets (2010) gave a new combinat...
read it

An Experimental Study of Algorithms for Geodesic Shortest Paths in the ConstantWorkspace Model
We perform an experimental evaluation of algorithms for finding geodesic...
read it

Maintaining the Union of Unit Discs under Insertions with NearOptimal Overhead
We present efficient data structures for problems on unit discs and arcs...
read it

Dynamic Maintenance of the Lower Envelope of PseudoLines
We present a fully dynamic data structure for the maintenance of lower e...
read it

Routing in Histograms
Let P be an xmonotone orthogonal polygon with n vertices. We call P a s...
read it

Approximate MinimumWeight Matching with Outliers under Translation
Our goal is to compare two planar point sets by finding subsets of a giv...
read it

Asymmetric Convex Intersection Testing
We consider asymmetric convex intersection testing (ACIT). Let P ⊂R^d ...
read it

Geometric Algorithms with Limited Workspace: A Survey
In the limited workspace model, we consider algorithms whose input resid...
read it

Five Proofs of Chernoff's Bound with Applications
We discuss five ways of proving Chernoff's bound and show how they lead ...
read it

Stabbing pairwise intersecting disks by five points
We present an O(n) expected time algorithm and an O(n n) deterministic ...
read it

Recognizing Generalized Transmission Graphs of Line Segments and Circular Sectors
Suppose we have an arrangement A of n geometric objects x_1, ..., x_n ⊆R...
read it

Combinatorics of Beaconbased Routing in Three Dimensions
A beacon is a pointlike object which can be enabled to exert a magnetic...
read it

TimeSpace TradeOffs for Computing Euclidean Minimum Spanning Trees
In the limitedworkspace model, we assume that the input of size n lies ...
read it

Improved TimeSpace Tradeoffs for Computing Voronoi Diagrams
Let P be a planar set of n sites in general position. For k∈{1,...,n1},...
read it
Wolfgang Mulzer
is this you? claim profile