### 224 Works

### Source Code

Herman Haverkort
The sources and the documentation of the software to go with the paper.

### Optimally fast incremental Manhattan plane embedding and planar tight span construction

David Eppstein
We describe a data structure, a rectangular complex, that can be used represent hyperconvex metric spaces that have the same topology (although not necessarily the same distance function) as subsets of the plane. We show how to use this data structure to construct the tight span of a metric space given as an n×n distance matrix, when the tight span is homeomorphic to a subset of the plane, in time O(n2), and to add a...

### Delaunay triangulation of imprecise points, preprocess and actually get a fast query time

Olivier Devillers
We propose a new algorithm to preprocess a set of n disjoint unit disks in O(n log n) expected time, allowing to compute the Delaunay triangulation of a set of n points, one from each disk, in O(n) expected time. Our algorithm has the same asymptotic complexity as previous ones for this problem, but our algorithm is much simpler and it runs faster in practice than a direct computation of the Delaunay triangulation.

### Spanners for geometric intersection graphs with applications

Martin Fürer & Shiva Prasad Kasiviswanathan
A ball graph is an intersection graph of a set of balls with arbitrary radii. Given a real numbert>1, we say that a subgraph G' of a graph G is a t-spanner of G, if for every pair of verticesu,v in G, there exists a path in G' of length at most t times the distance between u and v inG. In this paper, we consider the problem of efficiently constructing sparse spanners of ball...

### Hyperbolic Delaunay complexes and Voronoi diagrams made practical

Mikhail Bogdanov, Olivier Devillers & Monique Teillaud
We study Delaunay complexes and Voronoi diagrams in the Poincaré ball, a conformal model of the hyperbolic space, in any dimension. We elaborate on our earlier work on the space of spheres [CCCG'92], giving a detailed description of algorithms. We also study algebraic and arithmetic issues, observing that only rational computations are needed. All proofs are based on geometric reasoning; they do not resort to any use of the analytic formula of the hyperbolic distance....

### The Hausdorff core problem on simple polygons

Reza Dorrigiv, Stephane Durocher, Arash Farzan, Robert Fraser, Alejandro Lopez-Ortiz, J. Ian Munro, Alejandro Salinger & Matthew Skala
A polygon \(Q\) is a \(k\)-bounded Hausdorff Core of a polygon \(P\) if \(P\) contains \(Q\), \(Q\) is convex, and the Hausdorff distance between \(P\) and \(Q\) is at most \(k\). A Hausdorff Core of \(P\) is a \(k\)-bounded Hausdorff Core of \(P\) with the minimum possible value of \(k\), which we denote \(k_{\min}\). Given any \(k\) and any \(\varepsilon\gt 0\), we describe an algorithm for computing a \(k'\)-bounded Hausdorff Core (if one exists) in...

### Computational aspects of the Hausdorff distance in unbounded dimension

Stefan König
We study the computational complexity of determining the Hausdorff distance oftwo polytopes given in halfspace- or vertex-presentation in arbitrary dimension. Sub-sequently, a matching problem is investigated where a convex body is allowed to behomothetically transformed in order to minimize its Hausdorff distance to another one. For this problem, we characterize optimal solutions, deduce a Helly-type theorem and give polynomial time (approximation) algorithms for polytopes.

### Minimum area polyomino Venn diagrams

Bette Bultena, Matthew Klimesh & Frank Ruskey
Polyomino Venn (or polyVenn) diagrams are Venn diagrams whose curves are the perimeters of orthogonal polyominoes drawn on the integer lattice. Minimum area polyVenn diagrams are those in which each of the 2n intersection regions, in a diagram of n polyominoes, consists of exactly one unit square. We construct minimum area polyVenn diagrams in bounding rectangles of size 2r×2c whenever r, c ≥ 2. Our construction is inductive, and depends on two expansionresults. First, a...

### An optimal algorithm for computing angle-constrained spanners

Paz Carmi & Michiel Smid
Let S be a set of n points in Rd and let t>1 be a real number. A graph G=(S,E) is called a t-spanner for S, if for any two points p and q in S, the shortest-path distance in G between p andq is at most t|pq|, where |pq| denotes the Euclidean distance between p and q. The graph G is called θ-angle-constrained, if any two distinct edges sharing an endpoint make an angle...

### Flow computations on imprecise terrains

Anne Driemel, Herman Haverkort, Maarten Löffler & Rodrigo Silveira
We study water flow computation on imprecise terrains. We consider two approaches to modeling flow on a terrain: one where water flows across the surface of a polyhedral terrain in the direction of steepest descent, and one where water only flows along the edges of a predefined graph, for example a grid or a triangulation. In both cases each vertex has an imprecise elevation, given by an interval of possible values, while its (x,y)-coordinates are...

### Metric inequalities for polygons

Adrian Dumitrescu
Let A1,A2,…,An be the vertices of a polygon with unit perimeter, that is Σi |Ai Ai+1|=1. We derive various tight estimates on the minimum and maximum values of the sum of pairwise distances, and respectively sum of pairwise squared distances among its vertices. In most cases such estimates on these sums in the literature were known only for convex polygons. In the second part, we turn to a problem of Braß regarding the maximum perimeter...

### Steinitz theorems for simple orthogonal polyhedra

David Eppstein & Elena Mumford
We define a simple orthogonal polyhedron to be a three-dimensional polyhedron with the topology of a sphere in which three mutually-perpendicular edges meet at each vertex.By analogy to Steinitz's theorem characterizing the graphs of convex polyhedra, we find graph-theoretic characterizations of three classes of simple orthogonal polyhedra: corner polyhedra, which can be drawn by isometric projection in the plane with only one hidden vertex, xyz polyhedra, in which each axis-parallel line through a vertex contains...

### A counterexample to a geometric Hales-Jewett type conjecture

Vytautas Gruslys
Pór and Wood conjectured that for all \(k,l \ge 2\) there exists \(n \ge 2\) with the following property: whenever \(n\) points, no \(l + 1\) of which are collinear, are chosen in the plane and each of them is assigned one of \(k\) colours, then there must be a line (that is, a maximal set of collinear points) all of whose points have the same colour. The conjecture is easily seen to be true...

### Covering folded shapes

Oswin Aichholzer, Greg Aloupis, Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Michael Hoffmann, Anna Lubiw, Jack Snoeyink & Andrew Winslow
Can folding a piece of paper flat make it larger? We explore whether a shape S must be scaled to cover a flat-folded copy of itself. We consider both single folds and arbitrary folds (continuous piecewise isometries \(S\to\mathbb{R}^2\)). The underlying problem is motivated by computational origami, and is related to other covering and fixturing problems, such as Lebesgue's universal cover problem and force closure grasps. In addition to considering special shapes (squares, equilateral triangles, polygons...

### On projections of metric spaces

Mark Kozdoba
Let $X$ be a metric space and let $\mu$ be a probability measure on it. Consider a Lipschitz map $T: X \rightarrow \mathbb{R}^n$, with Lipschitz constant $\leq 1$. Then one can ask whether the image $TX$ can have large projections on many directions. For a large class of spaces $X$, we show that there are directions $\phi \in \mathbb S^{n-1}$ on which the projection of the image $TX$ is small on the average, with bounds...

### The Lebesgue universal covering problem

John C. Baez, Karine Bagdasaryan & Philip Gibbs
In 1914 Lebesgue defined a 'universal covering' to be a convex subset of the plane that contains an isometric copy of any subset of diameter 1. His challenge of finding a universal covering with the least possible area has been addressed by various mathematicians: Pál, Sprague and Hansen have each created a smaller universal covering by removing regions from those known before. However, Hansen's last reduction was microsopic: he claimed to remove an area of...

### Quasi-parallel segments and characterization of unique bichromatic matchings

Andrei Asinowski, Tillmann Miltzow & Günter Rote
Given n red and n blue points in general position in the plane, it is well-known that there is a perfect matching formed by non-crossing line segments. We characterize the bichromatic point sets which admit exactly one non-crossing matching. We give several geometric descriptions of such sets, and find an O(n log n) algorithm that checks whether a given bichromatic set has this property.

### Algorithms for ball hulls and ball intersections in normed planes

Pedro Martín & Horst Martini
Extending results of Hershberger and Suri for the Euclidean plane, we show that ball hulls and ball intersections of sets of $n$ points in normed planes can be constructed in $O(n \log n)$ time. In addition, we confirm that the 2-center problem with constrained circles for arbitrary normed planes can be solved in $O(n^2)$ time. Some ideas about the geometric structure of the ball hull in a normed plane are also presented.

### Flat norm decomposition of integral currents

Sharif Ibrahim, Bala Krishnamoorthy & Kevin Vixie
Currents represent generalized surfaces studied in geometric measure theory. They range from relatively tame integral currents representing oriented compact manifolds with boundary and integer multiplicities, to arbitrary elements of the dual space of differential forms. The flat norm provides a natural distance in the space of currents, and works by decomposing a $d$-dimensional current into $d$- and (the boundary of) $(d+1)$-dimensional pieces in an optimal way. Given an integral current, can we expect its at...

### Consistent labeling of rotating maps

Andreas Gemsa, Martin Nöllenburg & Ignaz Rutter
Dynamic maps that allow continuous map rotations, for example, on mobile devices, encounter new geometric labeling issues unseen in static maps before. We study the following dynamic map labeling problem: The input is an abstract map consisting of a set $P$ of points in the plane with attached horizontally aligned rectangular labels. While the map with the point set $P$ is rotated, all labels remain horizontally aligned. We are interested in a consistent labeling of...

### Towards plane spanners of degree 3

Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Cyril Gavoille, Anil Maheshwari & Michiel Smid
Let $S$ be a finite set of points in the plane. In this paper we consider the problem of computing plane spanners of degree at most three for $S$. • If $S$ is in convex position, then we present an algorithm that constructs a plane $\frac{3+4\pi}{3}$-spanner for $S$ whose vertex degree is at most 3. • If $S$ is the vertex set of a non-uniform rectangular lattice, then we present an algorithm that constructs a...

### Two-point L1 shortest path queries in the plane

Danny Z. Chen, Rajasekhar Inkulu & Haitao Wang
Let $P$ be a set of $h$ pairwise-disjoint polygonal obstacles with a total of $n$ vertices in the plane. We consider the problem of building a data structure that can quickly compute an $L_1$ shortest obstacle-avoiding path between any two query points $s$ and $t$. Previously, a data structure of size $O(n^2\log n)$ was constructed in $O(n^2\log^2 n)$ time that answers each two-point query in $O(\log^2 n+k)$ time, i.e., the shortest path length is reported...

### Counting and enumerating crossing-free geometric graphs

Manuel Wettstein
We describe a framework for constructing data structures which allow fast counting and enumeration of various types of crossing-free geometric graphs on a planar point set. The framework generalizes ideas of Alvarez and Seidel, who used them to count triangulations in time $O(2^nn^2)$ where $n$ is the number of points. The main idea is to represent geometric graphs as source-sink paths in a directed acyclic graph. The following results will emerge. The number of all...

### Classifying unavoidable Tverberg partitions

Boris Bukh, Po-Shen Loh & Gabriel Nivasch
Let $T(d,r) = (r-1)(d+1)+1$ be the parameter in Tverberg's theorem, and call a partition $\mathcal I$ of $\{1,2,\ldots,T(d,r)\}$ into $r$ parts a Tverberg type. We say that $\mathcal I$ occurs in an ordered point sequence $P$ if $P$ contains a subsequence $P'$ of $T(d,r)$ points such that the partition of $P'$ that is order-isomorphic to $\mathcal I$ is a Tverberg partition. We say that $\mathcal I$ is unavoidable if it occurs in every sufficiently long...

### Array-based compact data structures for triangulations: Practical solutions with theoretical guarantees

Luca Castelli Aleardi & Olivier Devillers
We consider the problem of designing space efficient solutions for representing triangle meshes. Our main result is a new explicit data structure for compactly representing planar triangulations: if one is allowed to permute input vertices, then a triangulation with $n$ vertices requires at most $4n$ references ($5n$ references if vertex permutations are not allowed). Our solution combines existing techniques from mesh encoding with a novel use of maximal Schnyder woods. Our approach extends to higher...