-
Article
Open AccessDynamic Connectivity in Disk Graphs
Let \(S \subseteq \mathbb {R}^2\) S ⊆ ...
-
Article
Open AccessMaximum Matchings in Geometric Intersection Graphs
Let G be an intersection graph of n geometric objects in the plane. We show that a maximum matching in G can be found in $$O\hspace{0.33325pt}...
-
Chapter and Conference Paper
Compatible Spanning Trees in Simple Drawings of \(K_n\)
For a simple drawing D of the complete graph \(K_n\) K n ...
-
Chapter and Conference Paper
Flip** Plane Spanning Paths
Let S be a planar point set in general position, and let \(\mathcal {P}(S)\) be the set of all plane straight-line paths with v...
-
Article
Open AccessNo-Dimensional Tverberg Theorems and Algorithms
Tverberg’s theorem states that for any \(k\ge 2\) k ≥ ...
-
Article
Open AccessDynamic Planar Voronoi Diagrams for General Distance Functions and Their Algorithmic Applications
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 ...
-
Article
Reachability Oracles for Directed Transmission Graphs
Let \(P \subset \mathbb {R}^d\)P⊂Rd be a set of n points in d dimensions such that each point \(p \in P\)p∈P has an associated radius\(r_p > 0\)rp>0. The transmission graphG for P is the directed graph with verte...
-
Chapter and Conference Paper
Routing in Histograms
Let P be an x-monotone orthogonal polygon with n vertices. We call P a simple histogram if its upper boundary is a single edge; and a double histogram if it has a horizontal chord from the left boundary to the ri...
-
Chapter and Conference Paper
Minimal Representations of Order Types by Geometric Graphs
In order to have a compact visualization of the order type of a given point set S, we are interested in geometric graphs on S with few edges that unequivocally display the order type of S. We introduce the concep...
-
Chapter and Conference Paper
An Experimental Study of Algorithms for Geodesic Shortest Paths in the Constant-Workspace Model
We perform an experimental evaluation of algorithms for finding geodesic shortest paths between two points inside a simple polygon in the constant-workspace model. In this model, the input resides in a read-on...
-
Article
Computational Aspects of the Colorful Carathéodory Theorem
Let \(C_1,\dots ,C_{d+1}\subset \mathbb {R}^d\) ...
-
Article
Routing in Unit Disk Graphs
Let \(S \subset \mathbb {R}^2\) S ...
-
Chapter and Conference Paper
Time-Space Trade-Offs for Computing Euclidean Minimum Spanning Trees
In the limited-workspace model, we assume that the input of size n lies in a random access read-only memory. The output has to be reported sequentially, and it cannot be accessed or modified. In addition, there i...
-
Chapter and Conference Paper
Combinatorics of Beacon-Based Routing in Three Dimensions
A beacon is a point-like object which can be enabled to exert a magnetic pull on other point-like objects in space. Those objects then move towards the beacon in a greedy fashion until they are either stuck at...
-
Chapter and Conference Paper
Recognizing Generalized Transmission Graphs of Line Segments and Circular Sectors
Suppose we have an arrangement \(\mathcal {A}\) A ...
-
Article
Open AccessFour Soviets Walk the Dog: Improved Bounds for Computing the Fréchet Distance
Given two polygonal curves in the plane, there are many ways to define a notion of similarity between them. One popular measure is the Fréchet distance. Since it was proposed by Alt and Godau in 1992, many var...
-
Chapter and Conference Paper
Delta-Fast Tries: Local Searches in Bounded Universes with Linear Space
Let \(w \in {\mathbb {N}}\) and $$U = \...
-
Chapter and Conference Paper
Time-Space Trade-Off for Finding the k-Visibility Region of a Point in a Polygon
We study the problem of computing the k-visibility region in the memory-constrained model. In this model, the input resides in a randomly accessible read-only memory of O(n) words, with
-
Article
Open AccessComputing the Fréchet Distance with a Retractable Leash
All known algorithms for the Fréchet distance between curves proceed in two steps: first, they construct an efficient oracle for the decision version; second, they use this oracle to find the optimum from a fi...
-
Chapter and Conference Paper
Routing in Unit Disk Graphs
Let \(S \subset \mathbb {R}^2\) S ⊂ ...
