Accepted Papers and Abstracts

Abstract: We study online routing algorithms on the Θ₆-graph and the half-Θ₆-graph (which is equivalent to a variant of the Delaunay triangulation). Given a source vertex s and a target vertex t in the Θ₆-graph (resp. half-Θ₆- graph), there exists a deterministic online routing algorithm that finds a path from s to t whose length is at most 2∥st∥ (resp. 2.89∥st∥) which is optimal in the worst case [Bose et al., Siam J. on Computing, 44(6)]. We propose alternative, slightly simpler routing algorithms that are optimal in the worst case and for which we provide an analysis of the average routing ratio for the Θ₆-graph and half-Θ₆-graph defined on a Poisson point process.

Abstract: A trajectory is a sequence of time-stamped locations. Measurement uncertainty is an important factor to consider when analysing trajectory data. We define an uncertain trajectory as a trajectory where at each time stamp the true location lies within an uncertainty region—a disk, a line segment, or a set of points. In this paper we consider discrete and continuous Fréchet distance between uncertain trajectories. We show that finding the largest possible discrete or continuous Fréchet distance among all possible realisations of two uncertain trajectories is NP-hard under all the uncertainty models we consider. Furthermore, computing the expected discrete or continuous Fréchet distance is #P-hard when the uncertainty regions are modelled as point sets or line segments. We also study the setting with time bands, where we restrict temporal alignment of the two trajectories, and give polynomial-time algorithms for largest possible and expected discrete and continuous Fréchet distance for uncertainty regions modelled as point sets.

Abstract: We provide a tight result for a fundamental problem arising from packing squares into a circular container: The critical density of packing squares in a disk is δ = 8/5 π ≈ 0.509. This implies that any set of (not necessarily equal) squares of total area A < 8/5 can always be packed into a unit disk; in contrast, for any &eps; > 0 there are sets of squares of area 8/5 + ε that cannot be packed. This settles the last case of packing circular or square objects into a circular or square container, as the critical densities for squares in a square (1/2), circles in a square (π/3 + √2 ≈ 0.539) and circles in a circle (1/2) have already been established. The proof uses a careful manual analysis, complemented by a minor automatic part that is based on interval arithmetic. Beyond the basic mathematical importance, our result is also useful as a blackbox lemma for the analysis of recursive packing algorithms.

Abstract: We provide the solution for a fundamental problem of geometric optimization by giving a complete characterization of worst-case optimal disk coverings of rectangles: For any λ ≥ 1, the critical covering area A^*(λ) is the minimum value for which any set of disks with total area at least A^*(λ) can cover a rectangle of dimensions λ * 1. We show that there is a threshold value λ₂ = 1.035797..., such that for λ < λ₂ the critical covering area A^* is A^*(λ) = 3 π (λ² / 16 + 5 / 32 + 9 / (256 λ²)), and for λ > λ₂, the critical area is A*(λ) = π (λ² + 2) / 4; these values are tight. For the special case λ = 1, i.e., for covering a unit square, the critical covering area is 195 π / 256 = 2.39301... . The proof uses a careful combination of manual and automatic analysis, demonstrating the power of the employed interval arithmetic technique.

Abstract: We consider the problem of coordinated motion planning for a swarm of simple, identical robots: From a given start grid configuration of robots, we need to reach a desired target configuration via a sequence of parallel, continuous, collision-free robot motions, such that the set of robots stays connected at all times. The objective is to minimize the makespan of the motion schedule, i.e., to reach the new configuration in a minimum amount of time. We show that this problem is NP-hard, even for deciding whether a makespan of 2 can be achieved, while it is possible to check in polynomial time whether a makespan of 1 can be achieved. We also provide a constant-factor approximation for fat configurations. Our algorithm achieves a constant stretch factor: If mapping the start configuration to the target configuration requires a maximum Manhattan distance of d, then the total duration of our overall schedule is O(d), which is optimal up to constant factors.

Abstract: We consider recognition and reconfiguration of lattice-based cellular structures by very simple robots with only basic functionality. The underlying motivation is the construction and modification of space facilities of enormous dimensions, where the combination of new materials with extremely simple robots promises structures of previously unthinkable size and flexibility. We present algorithmic methods that are able to detect and reconfigure arbitrary polyominoes, based on finite-state robots, while also preserving connectivity of a structure during reconfiguration. Specific results include methods for determining a bounding box, scaling a given arrangement, and adapting more general algorithms for transforming polyominoes.

Abstract: We investigate advanced algorithmic approaches for targeted drug delivery in a complex, maze- like environment, such as a vascular system. The basic scenario is given by a large swarm of micro-scale particles (“agents”) and a particular target region (“tumor”) within a system of passageways. Agents are too small to contain on-board power or computation and are instead controlled by a global external force that acts uniformly on all particles, such as an applied fluidic flow or electric field. The challenge is to deliver all agents to the target region with a minimum number of actuation steps. We provide a number of results for this challenge. We show that the underlying problem is NP-hard, which explains why previous work did not provide provably efficient algorithms. We also develop a number of advanced algorithmic approaches that greatly improve the worst-case guarantees for the number of required actuation steps.

Abstract: We present methods for achieving arbitrary reconfiguration of two particlesin convex workspaces, based on the use of external forces, such as a magnetic field or gravity: Upon actuation, each object is pushed in the same direction until it collides with an obstruction. This concept can be used for a wide range of applications in which particles do not have their own energy supply. A crucial challenge for achieving any desired target configuration is breaking global symmetry in a controlled fashion. Previous work made use of specifically placed barriers; however, introducing precisely located obstacles into the workspace is impractical for many scenarios. In this paper, we present a different, less intrusive method: making use of the interplay between static friction with a boundary and the external force to achieve arbitrary reconfiguration. Our key contributions are a precise characterization of the critical coefficient of friction that is sufficient for rearranging two particles in triangles, convex polygons, and regular polygons.

Abstract: We study the Trajectory Capture Problem (TCP), in which, for a given input set T of trajectories in the plane, and an integer k ≥ 2, we seek to compute a set of k points ("portals") to maximize the total length of all subtrajectories of T between pairs of portals. This problem naturally arises in trajectory analysis and summarization.
We show that TCP is NP-hard and then focus on attacking the TCP with integer linear programming to solve instances to provable optimality. We analyze this method on different classes of data, including benchmark instances that we generate. We demonstrate that we are able to compute provably optimal solutions for real-world instances.

Abstract: Let be an arrangement of n lines in the Euclidean plane. The k-level of consists of all intersection points v of lines in which have exactly k lines of passing below v. The complexity of the k-level in a line arrangement has been widely studied. In 1998 Dey proved an upper bound of O(n ⋅ (k + 1)^1/3). We investigate the complexity of k-levels in random line and hyperplane arrangements. When the arrangement is obtained from any fixed projective line arrangement of n lines by choosing a random cell to contain the south-pole, we prove an upper bound of O((k + 1)²) on the expected complexity of the k-level. As a byproduct we show that the complexity of any (≤ j)-zone in a d-dimensional simple arrangement of n hyperplanes is of order Θ((j+1) n^d-1). The classical zone theorem is the case j = 0. We also consider arrangements of great (d - 1)-spheres on the sphere ^d which are orthogonal to a set of random points on ^d. In this model we prove that the expected complexity of the k-level is of order Θ((k + 1)^d-1).

Abstract: In this article, we discuss classical theorems from Convex Geometry in the context of simple topological drawings of the complete graph K_n. In a simple topological drawing, any two edges share at most one point: either a common vertex or a point where they cross.
We present generalizations of Kirchberger's Theorem and the Erdős-Szekeres Theorem, a family of simple topological drawings with arbitrarily large Helly number, a new proof of the generalized Carathéodory's Theorem, and discuss further classical theorems from Convex Geometry in the context of simple topological drawings.

Abstract: Given a simple polygonal region P with n vertices, we present an efficient O(n log n) time and O(n) space algorithm for computing, over all values of θ, the maximum width of the θ-kernel(P), the locus of points in P from which any point of P can be reached by a (θ + π/2)-monotone path.

Abstract: We present a simple wavefront-like approach for computing multiplicatively weighted Voronoi diagrams of points and straight-line segments in the Euclidean plane. If the input sites may be assumed to be randomly weighted points then the use of a so-called overlay arrangement [Har-Peled & Raichel, Discrete Comput. Geom., 2015] allows to achieve an expected runtime complexity of O(n log⁴ n), while still maintaining the simplicity of our approach. We implemented the full algorithm for weighted points as input sites, based on CGAL. The results of an experimental evaluation of our implementation suggest O(n log² n) as a practical bound on the runtime. Our algorithm can be extended to handle also additive weights in addition to multiplicative weights.

Abstract: Reliable spanners can withstand huge failures, even when a linear number of vertices are deleted from the network. In case of failures, a reliable spanner may have some additional vertices for which the spanner property no longer holds, but this collateral damage is bounded by a fraction of the size of the attack. It is known that Ω(n log n) edges are needed to achieve this strong property, where n is the number of vertices in the network, even in one dimension. Constructions of reliable geometric (1 + ε)-spanners, for n points in ℝ^d, are known, where the resulting graph has O(n log n log log⁶ n) edges.
Here, we show randomized constructions of smaller size spanners that have the desired reliability property in expectation or with good probability. The new construction is simple, and potentially practical - replacing a hierarchical usage of expanders (which renders the previous constructions impractical) by a simple skip-list like construction. This results in a 1-spanner, on the line, that has linear number of edges. Using this, we present a construction of a reliable spanner in ℝ^d with O(n log log² n log log log n) edges.

Abstract: Some graph partitioning problems are known to be NP-hard for certain graph classes and polynomially solvable for others. We study the problem of partitioning the vertex set of a weighted cactus graph into clusters with bounded weights and present a polynomial-time algorithm that solves the problem with the optimal as well as some fixed number of clusters

Abstract: Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. manifolds defined as the zero set of some multivariate multivalued function f: ℝ^d → ℝ^d-n. A natural (and efficient) way to approximate an isomanifold is to consider its Piecewise-Linear (PL) approximation based on a triangulation of the ambient space ℝ^d. In this paper, we give conditions under which the PL-approximation of an isomanifold is topologically equivalent to the isomanifold. The conditions can always be met by taking a sufficiently fine triangulation .

Abstract: For d &#x 8714; ℕ, let S be a finite set of points in ℝ^d in general position. A set H of k points from S is a k-hole in S if all points from H lie on the boundary of the convex hull conv(H) of H and the interior of conv(H) does not contain any point from S. A set I of k points from S is a k-island in S if conv(I) ∩ S = I. Note that each k-hole in S is a k-island in S.
For fixed positive integers d, k and a convex body K in ℝ^d with d-dimensional Lebesgue measure 1, let S be a set of n points chosen uniformly and independently at random from K. We show that the expected number of k-islands in S is in O(n^d). In the case k = d + 1, we prove that the expected number of empty simplices (that is, (d + 1)-holes) in S is at most 2^d-1 ⋅ d! ⋅ (n choose d). Our results improve and generalize previous bounds by Bárány and Füredi (1987), Valtr (1995), Fabila-Monroy and Huemer (2012), and Fabila-Monroy, Huemer, and Mitsche (2015).

Abstract: We consider methods for finding a simple polygon of minimum (Min-Area) or maximum (Max-Area) possible area for a given set of points in the plane. Both problems are known to be NP-hard; at the center of the recent CG Challenge, practical methods have received considerable attention. However, previous methods focused on heuristic methods, with no proof of optimality. We develop exact methods, based on a combination of geometry and integer programming. As a result, we are able to solve instances of up to n = 25 points to provable optimality. While this extends the range of solvable instances by a considerable amount, it also illustrates the practical difficulty of both problem variantes.

Abstract: Motivated by recent work of Bukh and Nivasch on one-sided epsilon-approximants, we introduce the notion of weighted epsilon-nets. It is a geometric notion of approximation for point sets in ℝ^d similar to epsilon-nets and epsilon-approximations, where it is stronger than the former and weaker than the latter. The main idea is that small sets can contain many points, whereas large sets must contain many points of the weighted epsilon-net.
In this paper, we analyze weak weighted epsilon-nets with respect to convex sets and axis-parallel boxes and give upper and lower bounds on epsilon for weighted epsilon-nets of size two and three.

Abstract: We define and study a discrete process that generalizes the convex-layer decomposition of a planar point set. Our process, which we call "homotopic curve shortening" (HCS), starts with a closed curve (which might self-intersect) in the presence of a set P of point obstacles in ℝ², and evolves in discrete steps, where each step consists of (1) taking shortcuts around the obstacles, and (2) reducing the curve to its shortest homotopic equivalent.
We find experimentally that, if the initial curve is held fixed and P is chosen to be either a very fine regular grid or a uniformly random point set, then HCS behaves at the limit like the affine curve-shortening flow (ACSF). This connection between HCS and ACSF generalizes the link between "grid peeling" and the ACSF observed by Eppstein et al. (2017), which applied only to convex curves, and which was studied only for regular grids.
We prove that HCS satisfies some properties analogous to those of ACSF: HSC is invariant under affine transformations, preserves convexity, and does not increase the total absolute curvature. Furthermore, the number of self-intersections of a curve, or intersections between two curves (appropriately defined), does not increase. Finally, if the initial curve is simple, then the number of inflection points (appropriately defined) does not increase.

Abstract: We present several concatenation arguments for polyominoes and polycubes, and show their applications to setting lower and upper bounds on the growth constants of some of their families, whose enumerating sequences are pseudo sub- or super-multiplicative. \emph{Inter alia}, we provide bounds on the growth constants of general, tree, and convex polyominoes, and general polycubes.

Abstract: Task allocation is an important aspect of many multi-robot systems. In this paper, we consider a new task allocation problem that appears in multi-robot aerial cinematography. The main goal is to distribute a set of tasks (shooting actions) among the team members optimizing a certain objective function. The tasks are given as sequences of waypoints with associated time intervals (scenes). We prove that the task allocation problem maximizing the total filmed time by k aerial robots (drones) can be solved in polynomial time when the drones do not require battery recharge. We also consider the problem in which the drones have a limited battery endurance and must periodically go to a static base station. For this version, we show how to solve the problem in polynomial time when only one drone is available.

Abstract: Let G=(V,E) be a plane graph. We say that a face f of G is guarded by an edge vw if at least one vertex from {v,w} is on the boundary of f. For a planar graph class C we ask for the minimal number of edges needed to guard all faces of any n-vertex graph in C. In this extended abstract we provide new bounds for two planar graph classes, namely the quadrangulations and the stacked triangulations.

Abstract: A geometric triangulation of a Riemannian manifold is a triangulation where the interior of each simplex is totally geodesic. Bistellar moves are local changes to the triangulation which are higher dimensional versions of the flip operation of triangulations in a plane. We show that geometric triangulations of a compact hyperbolic, spherical or Euclidean manifold are connected by geometric bistellar moves (possibly adding or removing vertices), after taking sufficiently many barycentric subdivisions. For dimension 2 and 3, we show that geometric triangulations of such manifolds are directly related by geometric bistellar moves.

Abstract: Hadwiger and Debrunner showed that for families of convex sets in ℝ^d with the property that among any p of them some q have a common point, the whole family can be stabbed with p - q + 1 points if p ≥ q ≥ d + 1 and (d − 1) p < (q − 1). This generalizes a classical result by Helly. We show how such a stabbing set can be computed for convex polygons of constant size in the plane in O((p − q + 1) n^4/3 log^2+ε(n) + p³) expected time. For convex polyhedra in ℝ³, the method yields an algorithm running in O((p − q + 1) n^{13/5 + ε} + p⁴) expected time. We also show that analogous results of the Hadwiger and Debrunner (p,q)-theorem hold in other settings, such as convex sets in ℝ^d ⨯ ℤ^k or abstract convex geometries.

Abstract: Weak unit disk contact graphs are graphs that admit representing nodes as a collection of internally disjoint unit disks whose boundaries touch if there is an edge between the corresponding nodes. In this work we focus on graphs without embedding, i.e., the neighbor order can be chosen arbitrarily. We give a linear time algorithm to recognize whether a caterpillar, a graph where every node has distance ≤1 to a central path, allows a weak unit disk contact representation. On the other hand, we show that it is NP-hard to decide whether a tree allows such a representation.

Abstract: We perform an experimental study on the practical nature of the NP-hard problem of finding a Minimum Weight Triangulation (MWT) of a planar point set: Can we deliberately construct practically difficult instances? This requires identifying point sets for which all of a number of previously developed exact and heuristic methods simultaneously encounter a combination of pitfalls. We show that for instances of medium size, this seems unlikely, implying that one of several alternative methods may offer a path to an optimal solution. This complements recent work on the practical performance of these heuristic methods for specific classes of large benchmark instances, indicating that MWT problems may indeed be practically easier to solve than implied by its NP-hard complexity.

Abstract: We study the flip graph of higher order Delaunay triangulations. A triangulation of a set S of n points in the plane is order-k Delaunay if the circumcircle of every triangle contains at most k points of S in its interior. The flip graph of S has one vertex for each possible triangulation of S, and an edge connects two vertices when the two corresponding triangulations can be transformed into each other by a flip (i.e., exchanging the diagonal of a convex quadrilateral by the other one). We show that, even though the order-k flip graph can be disconnected for k ≥ 3, any order-k triangulation can be transformed into another one by at most k − 1 flips, such that the intermediate triangulations are of order at most 2k − 2, in the following settings: (1) for any k ≥ 0 when S is in convex position, and (2) for any point set S when k ≤ 5.

Abstract: We want to compare embedded graphs at a global and a local scale. The graph distances presented in [5] (ISAAC 2019) compare two graphs by mapping one graph onto the other and taking the maximum Fréchet distance between edges and their mappings. For this, the graph mapping is chosen such that the bottleneck distance is minimized. Here, we present two approaches to compute graph mappings subject to additional optimization criteria in order to improve distances locally.

Abstract: We present a new algorithm that reconfigures between any two edge-connected configuration of n sliding squares within their bounding boxes. The algorithm achieves the reconfiguration by means of Θ(n²) slide moves. A visual simulator and a set of experiments allows us to compare the performance over different shapes, showing that in many practical cases the number of slide moves grows significantly slower than in others as n increases.

Abstract: A generalization of the Ham-Sandwich Theorem by Barany, Hubard, and Jeronimo [DCG 2008] states that given any d measurable sets in ℝ^d that are convex and well-separated, and any given α₁, ..., α_d in [0,1], there is a unique hyperplane that cuts off a respective fraction α₁, ..., α_d from each set. Steiger and Zhao [DCG 2010] proved a discrete analogue, the Generalized Ham-Sandwich theorem. They gave an algorithm to find the hyperplane in time O(n (log n)^d-3), where n is the input size. The computational complexity of this search problem in high dimensions is open, unlike that of the Ham-Sandwich problem, which is now known to be PPA-complete.
Recently, Fearley, Gordon, Mehta, and Savani [ICALP 2019] introduced a new sub-class of CLS (Continuous Local Search): Unique End-of-Potential Line (UEOPL) captures problems in CLS that have unique solutions. We show that for the Generalized Ham-Sandwich theorem, the search problem of finding the dividing hyperplane lies in UEOPL. This provides the first non-trivial upper bound on the problem and places it in the company of classic search problems.

Abstract: Let G be a graph such that every vertex of G is equipped with a set of FPQ-trees encoding hierarchical embedding constraints for its incident edges. We study the problem of testing whether G admits a planar embedding such that, for each vertex v of G, the cyclic order of the edges incident to v is described by at least one of the FPQ-trees associated with v. We prove that the problem is FPT for biconnected graphs, where the parameters are the treewidth of G and the number of FPQ-trees associated with every vertex. We also show that the problem is NP-complete if parameterized by the number of FPQ-trees only, and W[1]-hard if parameterized by the treewidth only.

Abstract: We prove that the edge-length ratio of 2-trees is not bounded by a constant, which answers a question of Lazard et al. When the edge-length ratio is computed by taking into account only adjacent edges, we prove that any 2-tree admits a planar straight-line drawing whose edge-length ratio is at most 4 + ε for an arbitrarily small ε > 0.

Abstract: Simple drawings are drawings of graphs in which all edges have at most one common point (either a common endpoint, or a proper crossing). It has been an open question whether every simple drawing of a complete bipartite graph K_m,n contains a plane spanning tree as a subdrawing. We answer this question to the positive by showing that for every simple drawing of K_m,n and for every vertex v in that drawing, the drawing contains a shooting star rooted at v, that is, a plane spanning tree with all incident edges of v.

Abstract: Given a sequence of points P = {p₁, p₂, ..., p_n}, we are interested in the number of different Delaunay triangles occurring when considering the Delaunay triangulations of all contiguous subsequences within P. While clearly point sets and orderings with Θ(n²) Delaunay triangles exist, we prove that for an arbitrary point set in random order, the expected number of Delaunay triangles is O(n log n).

Abstract: Let S be a set of n points in general position in the plane. Suppose that each point of S has been assigned one of k ≥ 3 possible colors and that there is the same number, m, of points of each color class. A triangle with vertices on S is empty if it does not contain points of S in its interior and it is rainbow if all its vertices have different colors. Let f(k,m) be the minimum number of empty rainbow triangles determined by S. In this paper we show that f(k,m) = Θ(k³). Furthermore we give a construction which does not contain an empty rainbow quadrilateral.

Abstract: We investigate how the complexity of Euclidean TSP for point sets P in the strip (−∞, +∞) × [0, δ] depends on the strip width δ. We prove that if the points have distinct integer x-coordinates, a shortest bitonic tour (which can be computed in O(n log² n) time using an existing algorithm) is guaranteed to be a shortest tour overall when δ ≤ 2√2, a bound which is best possible.

Abstract: We present C++ implementations of two algorithms for computing straight skeletons in the plane, based on exact arithmetic. One code, named Surfer, can handle multiplicatively weighted planar straight-line graphs (PSLGs) while our second code, Monos, is specifically targeted at monotone polygons. Both codes are available on GitHub. We sketch implementational and engineering details and discuss the results of an extensive performance evaluation in which we compared Surfer and Monos to the straight-skeleton package included in CGAL. Our tests provide ample evidence that both implementations can be expected to be faster and to consume significantly less memory than the CGAL code.

Abstract: We prove that the induced subtree isomorphism problem is NP-complete for penny graphs and chordal graphs as text graphs. As a step in the proofs, we reprove that the problem is NP-complete if the text graph is planar. For many other graph classes NP-completeness follows, as they contain one of the above three classes as a subclass, e.g., segment intersection graphs and coin graphs (contain planar graphs) or unit disk graphs (contain penny graphs).

Abstract: Melodic similarity measurement is of key importance in Music Information Retrieval. In this paper, we use geometric matching techniques to measure the similarity between two melodies. We propose efficient algorithms for two optimization problems inspired in two operations on melodies: linear scaling and compressing. In the scaling problem, a incoming query melody is scaled forward in the horizontal direction so that the similarity measure between the query and the reference melody is minimized. The compressing problem asks for a subset of the notes of a given melody that minimizes the cost of the matching between the reference melody and the selected notes.

Abstract: We study the existence of an n-fold rotational symmetric placement of a symmetric graph in the plane allowing a continuous deformation that preserves the symmetry and the distances between adjacent vertices. We show that such a flexible placement exists if and only if the graph has a NAC-colouring satisfying an additional property on the symmetry; a NAC-colouring is a surjective edge colouring by two colours such that every cycle is either monochromatic, there are at least two edges of each colour.

Abstract: We study disjoint compatible noncrossing geometric matchings of simple polygons. That is, given a simple polygon P we want to draw a set of pairwise disjoint straight line edges with endpoints on the vertices of P such that these new edges neither cross nor contain any edge of the polygon. We prove NP-completeness of deciding whether there is such a perfect matching. For any n-vertex polygon we show that such a matching with ≤ (n - 4) / 8 edges is not maximal, that is, it can be extended by another compatible matching edge. Complementing this we construct polygons with maximal matchings with n / 6 edges. Finally we consider a related problem. We prove that it is NP-complete to decide whether a noncrossing geometric graph G admits a set of compatible noncrossing edges such that G together with these edges has minimum degree 5.

Abstract: We study the problem of covering a set of line segments with a few (up to four) axis-parallel, unit-sized squares in the plane. Covering line segments with two squares has been previously studied, however, little is known for three or more squares. Our original motivation for the line segment covering problem comes from trajectory analysis. We study two trajectory covering problems: a data structure on the trajectory that efficiently answers whether a query subtrajectory is coverable, and an algorithm to compute its longest coverable subtrajectory.

Abstract: We show that every planar graph can be represented by a monotone topological 2-page book embedding where at most 15n / 16 (of potentially 3n - 6) edges cross the spine exactly once.

Abstract: We study problems related to colouring bottomless rectangles. Our main result shows that there is no number m and semi-online algorithm that could colour a family of nested bottomless rectangles from below with a bounded number of colours such that every m-fold covered point is covered by at least two colours. We also prove several similar results that follow from a more abstract arborescence colouring problem, which is interesting on its own. We show that there is no semi-online algorithm for colouring the vertices of an arborescence without a long monochromatic path when the vertices are presented in a leaf-to-root order. The lower bounds are complemented with simple optimal upper bounds for semi-online algorithms from other directions.

Abstract: In [8], Gangopadhyay et al. proved that there exist Ω(2^d √ d) crossing pairs of hyperedges in any d-dimensional rectilinear drawing of the complete d-uniform hypergraph having 2d vertices. Here, we improve this lower bound by showing that there exist Ω (2^d d) crossing pairs of hyperedges for the same. In [4], Anshu et al. conjectured that among all d-dimensional rectilinear drawings of a complete d-uniform hypergraph having n vertices, the number of crossing pairs of hyperedges is maximized if all its vertices are placed on the d-dimensional moment curve and proved this conjecture for d = 3. It is trivially true for d = 2. We prove that their conjecture is valid for d = 4 by using Gale transform. We establish that the maximum d-dimensional rectilinear crossing number of a complete d-partite d-uniform balanced hypergraph is (2^(d-1) - 1) (n choose 2)^d, where n denotes the number of vertices in each part. We then prove that finding the maximum d-dimensional rectilinear crossing number of an arbitrary d-uniform hypergraph is NP-hard and give a randomized scheme to create a d-dimensional rectilinear drawing of a d-uniform hypergraph, H producing the number of crossing pair of hyperedges up to a constant factor of the maximum d-dimensional rectilinear crossing number of H.

Abstract: We consider minimal-perimeter lattice animals, and provide a set of conditions that are sufficient for a lattice to have the property that inflating all minimal-perimeter animals of a certain size yields (without repetitions) all minimal-perimeter animals of a new, larger size. We demonstrate this result on the two-dimensional hexagonal lattice. In addition, we provide two efficient algorithms for counting minimal-perimeter polyhexes.

Abstract: We present the first three-dimensional model for hybrid programmable matter, in which small active robots with the computational capabilities of finite automata and very limited sensing operate on a structure of passive tiles. The model is an extension of the two-dimensional model of Gmyr et al. [DNA 2018], whose hexagonal tiles on the triangular lattice translate to hollow rhombic dodecahedral tiles on the face-centered cubic lattice. Following the idea of Gmyr et al., we initiate the research in this model by considering a single robot that can navigate through the structure, pick up tiles, and place them somewhere else to transform the structure. Contrary to the two-dimensional case, where the robot can always find a tile to move while preserving connectivity, we show that such a tile cannot be found in the three-dimensional model without an additional helper tile. We then show how the robot can construct a line with the help of such a tile in O(n³) rounds, where n is the number of tiles. A line lends itself as an intermediate structure to build more complex objects such as triangles or cubes. Our presentation is accompanied by an implementation in a 3D simulator we specifically developed for our hybrid model.

Abstract: A universal cover for a family of triangles is a convex shape that contains a congruent copy of each triangle T ∈ . We conjecture that for any family of triangles (of bounded area) there is a triangle that forms a universal cover for of smallest possible area. We prove this conjecture for all families of two triangles, and for the family of triangles that fit in the unit circle.

Abstract: Given two shapes A and B in the plane with Hausdorff distance 1, is there a shape S with Hausdorff distance 1/2 to and from A and B? The answer is always yes, and depending on convexity of A and/or B, S may be convex, connected, or disconnected. We show a generalization of this result and a few others about Hausdorff distances, middle shapes, and related properties. We also show that the implied morph has a bounded rate of change.

Abstract: A graph has an edge-contact representation with polygons if its vertices can be represented by interior-disjoint polygons such that two polygons share a common edge if and only if the corresponding vertices are adjacent. In this work we study representations in 3D.
We show that every graph has an edge-contact representation with polygons in 3D, while this is not the case if we additionally require that the polygons are convex. In particular, we show that every graph containing K₅ as a subgraph does not admit a representation with convex polygons. On the other hand, K_4,4 admits such a representation, and so does every K_n where every edge is subdivided by a vertex. We also construct an infinite family (G_n) of graphs where G_n has n vertices, 6n - o(n) edges, and admits an edge-contact representation with convex polygons in 3D.

Abstract: Let V ⊂ ℝ² be a set of n sites in the plane. The unit disk graph DG(V) of V is the graph with vertex set V in which two sites v and w are adjacent if and only if their Euclidean distance is at most 1. We develop a compact routing scheme ℛ for DG(V). The routing scheme ℛ preprocesses DG(V) by assigning a label l(v) to every site v in V. After that, for any two sites s and t, the scheme ℛ must be able to route packet from s to t as follows: given the label of a current vertex r (initially, r = s) and the label of the target vertex t, the scheme determines a neighbor r' of r. Then, the packet is forwarded to r', and the process continues until the packet reaches its desired target t. The resulting path between the source s and the target t is called the routing path of s and t. The stretch of the routing scheme is the maximum ratio of the total Euclidean length of the routing path and of the shortest path in DG(V), between any two sites s, t in V. We show that for any given ε>0, we can construct a routing scheme for DG(V) with stretch 1 + ε and label size O(log D log³ n / log log n) (the constant in the O-Notation depends on ε). In the past, several routing schemes for unit disk graphs have been proposed. Our scheme is the first one to achieve poly-logarithmic label size and arbitrarily small stretch without storing any additional information in the packet.

Abstract: Given a set of points P in ℝ^d for an arbitrary d, the 1-center problem or minimum enclosing ball problem (MEB) asks to find a ball B^* of minimum radius r^* which covers all of P. Kumar et. al. [5] and Bǎdoiu and Clarkson [1] simultaneously developed core-set based (1 + ε)-approximation algorithms. While Kumar et al. achieve a slightly better theoretical runtime of O(n d / ε + 1 / ε^4.5 log 1 / ε), Bǎdoiu and Clarkson have a stricter bound of ⌈2 / ε⌉ on the size of their core-set, which strongly affects run-time constants. We give a gradient-descent based algorithm running in time O(n d / ε) based on a geometric observation that was used first for a 2-center streaming algorithm by Kim and Ahn [4]. Our approach can be extended to the k-center problem to obtain a (1 + ε)-approximation in time n d 2^{O(k / ε log k)}.

Abstract: Two plane drawings of geometric graphs on the same set of points are called disjoint compatible if their union is plane and they do not have an edge in common. For a given set S of 2n points two plane drawings of perfect matchings M₁ and M₂ (which do not need to be disjoint nor compatible) are disjoint tree-compatible if there exists a plane drawing of a spanning tree T on S which is disjoint compatible to both, M₁ and M₂. We show that the disjoint tree-compatible graph of all perfect geometric matchings on 2n points in convex position is connected if and only if 2n ≥ 10. Moreover, in that case the diameter of this graph is either 4 or 5, independent of n.

Abstract: Given a point set P and a natural integer k, are k closed convex polygons sufficient to partition the convex hull of P such that each polygon does not contain a point in P? What if the vertices of these polygons are constrained to be points of P? By allowing degenerate point sets, where three points may be on a line, we show that the first decision problem is NP-hard and the second NP-complete.

Abstract: We give algorithms to compute the Fréchet distance of trees with known root and graphs with bounded tree width. Our algorithms run in O(n²) time for trees with fixed root and of bounded degree, and O(n₂ √(n log n)) time for trees of arbitrary degree. For graphs of bounded tree width we show one can compute the Fréchet distance in FPT time.

Abstract: For a set of curves, Ahn et al. introduced the notion of a middle curve and gave algorithms computing these with run time exponential in the number of curves. Here we study the computational complexity of this problem: we show that it is NP-complete and give approximation algorithms.

Abstract: Let D = {d₁, ..., d_n } be a set of n disks in the plane, and let C = {c₁, ..., c_n} be their centers. The transmission graph G = (C, E) has the centers of D as its vertex set C, and a directed edge (c_i,c_j) if and only if c_j lies in the disks associated with c_i. A t-spanner G' for G is a sparse subgraph of G such that for any two vertices p, q connected by a directed path in G, there is a directed path from p to q in G' of length at most t times the length of the path from p to q in G. In this paper, we consider the problem of computing a t-spanner with a linear number of edges and bounded in-degree for transmission graphs. We show that the well-known Path-Greedy algorithm produces such a t-spanner for transmission graphs, thus, providing a much simpler method than ones that are currently in use. In addition, we show that the weight of the resulting t-spanner is O(log n ⋅ wt(MST(D)) (1 + Ψ)), where Ψ is the ratio between the largest and smallest disk radii, and wt(MST(D)) is the weight of the MST built over the centers of the disks. To the best of our knowledge, this is the first upper bound on the weight of a t-spanner for transmission graphs.

Abstract: We introduce the diverse Voronoi partition problem: for a given set of colored points and a number k, determine a set of k point sites so that the Voronoi cells of these sites contain as many colors as possible. We show that the problem is already NP-complete for points colored in four colors on a line, and give polynomial-time algorithms for a few special cases.

Abstract: The predominant approach to find decent solutions for hard optimization problems is to compute an approximation. An alternative approach is resource augmentation (a form of problem relaxation), where you consider an optimal solution subject to slightly weaker problem constraints. This alternative approach has considerably less traction in theoretical computer science than approximation algorithms have. We study optimization problems with natural resource augmentations and show that the bit precision of their optimal solution can be bounded using smoothed analysis of their augmentation. Our results imply that for realistic problem constraints, the optimal solution to a relaxed version of a problem yields an optimal solution for the original problem. We hope our results help solidify the traction that resource augmentation has in theoretical computer science.

Abstract: Motivated by applications in combinatorial geometry, we consider the following question: Let λ = (λ₁, ..., λ_m) be an m-partition of n, let S_i ⊆ ℂ^λ_i be finite sets, and let S := S₁ × S₂ × ... × S_m ⊆ ℂⁿ be the multi-grid defined by S_i. If p is a degree d polynomial with n variables, how many zeros can p have on S?
We show that, except for a special family of polynomials - that we call λ-reducible - a natural generalization of the Schwartz-Zippel-DeMillo-Lipton Lemma holds. Moreover, we develop a symbolic algorithm to detect λ-reducibility for a special case. Along the way, we also present a multivariate generalization of Combinatorial Nullstellensatz, which might be of independent interest.

Abstract: In the context of computing schematic maps, we consider the problem of computing orthogonal polygons with k vertices for a given simple orthogonal polygon with n vertices, such that the result has minimal homotopy area. We compare allowing self-intersections to the case that requires the result to be simple and present an O(n⁵k)-time algorithm to compute the optimal result in the nonsimple case.

Abstract: We revisit a data structure from de Berg, Mehrabi and Ophelders that can store a polyline trajectory π, such that for any directed horizontal query segment pq one can compute the Frechét distance between π and pq in polylogarithmic time. We extend their analysis of the geometric constructions that can realise the Frechét distance between π and pq and prove that in fact, their data structure only requires O(n^3/2) as opposed to O(n²) space.

Abstract: We study two new versions of independent and dominating set problems on vertex-colored interval graphs, namely f-Balanced Independent Set} (f-BIS) and f-Balanced Dominating Set} (f-BDS). Let G = (V, E) be a vertex-colored interval graph with a k-coloring γ: V → {1, ..., k} for some k ∈ ℕ. A subset of vertices S ⊆ V is called f-balanced if S contains f vertices from each color class. In the f-BIS and f-BDS problems, the objective is to compute an independent set or a dominating set that is f-balanced. We show that both problems are NP-complete even on proper interval graphs. For the BIS problem on interval graphs, we design two FPT algorithms, one parameterized by (f, k) and the other by the vertex cover number of G. Moreover, we present a 2-approximation algorithm for a slight variation of BIS on proper interval graphs.

Abstract: We study the following combinatorial problem. Given a set of n y-monotone curves, which we call wires, a tangle determines the order of the wires on a number of horizontal layers such that the orders of the wires on any two consecutive layers differ only in swaps of neighboring wires. Given a multiset L of swaps (that is, unordered pairs of wires) and an initial order of the wires, a tangle realizes L if each pair of wires changes its order exactly as many times as specified by L. Finding a tangle that realizes a given multiset of swaps and uses the least number of layers is known to be NP-hard. We show that it is even NP-hard to decide if a realizing tangle exists.

Abstract: The sparse regression problem, also known as best subset selection problem, can be cast as follows: Given a set S of n points in ℝ^d, a point y in ℝ^d, and an integer 2 ≤ k ≤ d, find an affine combination of at most k points of S that is nearest to y. We describe a O(n^{k - 1} log^{d - k + 2} n)-time randomized (1 + ε)-approximation algorithm for this problem with d and ε constant. This is the first algorithm for this problem running in time o(n^k). Its running time is similar to the query time of a data structure recently proposed by Har-Peled, Indyk, and Mahabadi (ICALP'18), while not requiring any preprocessing. Up to polylogarithmic factors, it matches a conditional lower bound relying on a conjecture about affine degeneracy testing. In the special case where k = d = O(1), we also provide a simple O_δ(n^{d - 1 + δ})- time deterministic exact algorithm, for any δ > 0. Finally, we show how to adapt the approximation algorithm for the sparse linear regression and sparse convex regression problems with the same running time, up to polylogarithmic factors.

Abstract: Given a set of points in the plane, we are interested in matching them with straight line segments. We focus on perfect (all points are matched) non-crossing (no two edges intersect) matchings. Apart from the well known MinMax variation, where the length of the longest edge is minimized, we extend work by looking into different optimization variants such as MaxMin, MinMin, and MaxMax. We consider both the monochromatic and bichromatic versions of these problems and provide efficient algorithms for various input point configurations.

Abstract: We consider the problem of drawing an outerplanar graph with n vertices with at most one bend per edge if the outer face is already drawn as a simple polygon with m corners. We prove that it can be decided in O(mn) time if such a drawing exists. In the positive case, our algorithm also outputs such a drawing.

Abstract: Slanted and curved nonograms are a new type of picture puzzles introduced by van de Kerkhof et al. (2019). They consist of an arrangement of lines or curves within a frame B, where some of the cells need to be colored in order to obtain the solution picture. Up to two clues are attached as numeric labels to each line on either side of B. In this paper we study the algorithmic problem of optimizing or deciding the existence of a placement of the given clue labels to a nonogram. We provide polynomial-time algorithms for restricted cases and prove NP-completeness in general.

Abstract: Given a set of k points A in ℝⁿ together with a positive weight function w: A → R, the Fermat distance function is φ(x) = sum_{a ∈ A} w(a) ∥x - a∥. A classic problem in facility location is finding the Fermat point P, the point that minimizes the function φ. We present algorithms to compute an ε-approximation of the Fermat point, that is, a point p satisfying ∥p - P∥ < ε. Our algorithms are based on the subdivision paradigm, which we combine with Newton methods, used for speed-ups and certification. For r > φ(P), we further consider the r-level set φ^-1(r), called a k-ellipse. We introduce a new algorithm to compute ε-isotopic approximations of k-ellipses in the plane. Our algorithms are certified in sense of interval methods.

Abstract: We study a motion planning problem for point objects controlled by an external repulsive force. Given a point object zeta inside a simple polygon P, a repulsor r (also represented by a point in P) moves zeta by always pushing it away from r. When zeta hits the boundary of P, then zeta slides along the boundary continuously increasing the distance to r until this is no longer possible. For a fixed polygon P and starting position s of zeta inside P, we define the repulsion region as the set of points in P that can be reached by zeta by placing a repulsor r anywhere inside P (and keeping the position of r fixed throughout the motion). In this paper we show that, for a specific class of polygons, the worst case complexity of the repulsion region is Θ(n²) and the repulsion region can be computed in O(n² log n) time, where n is the complexity of the polygon.

Abstract: Given a set of agents that have fixed locations but can rotate at unit speed, we aim to find an efficient schedule such that every pair of agents has looked at each other. We present schedules and lower bounds for different geometric settings.

Abstract: The Salzburg Database is a repository of polygonal areas of various classes and sizes, with and without holes. Positive weights are assigned to all edges of all polygons. We introduce this collection and briefly describe the generators that produced its polygons. The source codes for all generators as well as the polygons generated are publicly available.

Abstract: In 2014 Solomon and Elkin constructed a shortcutting scheme for weighted trees which results in a 1-spanner for the tree metric induced by the input tree. The spanner has logarithmic lightness, logarithmic diameter, a linear number of edges and bounded degree (provided the input tree has bounded degree). This spanner has been applied in a series of papers devoted to designing bounded degree, low-diameter, low-weight (1 + ε)-spanners in Euclidean and doubling metrics. In this article, we present a simple local routing algorithm for this tree metric spanner. The algorithm has a routing ratio of 1, is guaranteed to terminate after O(log n) hops and requires O(Δ log n) bits of storage per vertex where Δ is the maximum degree of the tree on which the spanner is constructed.

Abstract: Let P be a finite set of points in the plane. For any spanning tree T on P, we denote by |T| the Euclidean length of T. Let T_opt be a noncrossing spanning tree of maximum length for P. We show how to construct a noncrossing spanning tree T_a with |T_a| ≥ δ ⋅ |T_opt|, with δ = 0.512. We also show how to improve this bound when the points lie in a thin rectangle.

Abstract: Let P ⊆ ℝ² be a set of points and T be a spanning tree of P. The stabbing number of T is the maximum number of intersections any line in the plane determines with the edges of T. The tree stabbing number of P is the minimum stabbing number of any spanning tree of P. We prove that the tree stabbing number is not a monotone parameter, i.e., there exist point sets P ⊊ P' such that Tree-Stab{P} > Tree-Stab{P'}, answering a question by Eppstein [4, Open Problem 17.5].

Abstract: A star-simple drawing of a graph is a drawing in which adjacent edges do not cross. In contrast, there is no restriction on the number of crossings between two independent edges. When allowing empty lenses (faces bounded by exactly two edges), two independent edges may cross arbitrarily many times in a star-simple drawing. We consider star-simple drawings of K_n without empty lenses. In this setting we prove an upper bound of e((n − 4)!) on the maximum number of crossings between any pair of edges. It follows that the total number of crossings is finite and upper bounded by n!.

Abstract: Every graph that admits a topological drawing also admits a simple topological drawing. It is easy to observe that every 1-planar graph admits a 1-plane simple topological drawing. It has been shown that 2-planar graphs and 3-planar graphs also admit 2-plane and 3-plane simple topological drawings, respectively. However, nothing has been proved for simple topological drawings of k-planar graphs for k ≥ 4. In fact, it has been shown that there exist 4-planar graphs which do not admit a 4-plane simple topological drawing, and the idea can be extended to k-planar graphs for k > 4. We prove that there exists a function f: ℕ → ℕ such that every k-planar graph admits an f(k)-plane simple topological drawing for all k ∈ ℕ. This answers a question posed by Schaefer.

Abstract: We present a technique for the enumeration of all isotopically distinct ways of tiling, with disks, a hyperbolic surface of finite genus, possibly nonorientable and with punctures and boundary. This provides a generalization of the enumeration of Delaney-Dress combinatorial tiling theory on the basis of isotopic tiling theory. To accomplish this, we derive representations of the mapping class group of the orbifold associated to the symmetry group of the tiling under consideration as a set of algebraic operations on certain generators of the symmetry group. We derive explicit descriptions of certain subgroups of mapping class groups and of tilings as embedded graphs on orbifolds. We further use this explicit description to present an algorithm that we illustrate by producing an array of examples of isotopically distinct tilings of the hyperbolic plane with symmetries generated by rotations that are commensurate with the prominent Primitive, Diamond and Gyroid triply-periodic minimal surfaces, outlining how the approach yields an enumeration. We also present the corresponding 3-periodic graphs on these surfaces.

Abstract: The recently introduced k-Fréchet distance extends the well-known Fréchet distance to objects of rearranged pieces. We focus on a variant of this, namely the cut distance, where the input curves are cut into subcurves, which are then matched regarding their similarity with respect to the weak Fréchet distance. It is NP-hard to decide the cut distance of two curves, however, we give a polynomial time algorithm in case the curves are only cut into two subcurves.

Abstract: A polygon is called C-oriented if the orientations of all its edges stem from a pre-defined set C. The schematization of a polygon is then a C-oriented polygon that describes and simplifies the shape of the input polygon with respect to given hard and soft constraints. We study the case that the C-oriented polygon needs to contain the input polygon such that it is tight in the sense that it cannot be shrunk without starting overlapping with the input polygon; we call this a tight C-hull of the polygon. We aim at one that optimally balances the number of bends, the total edge length and the enclosed area. For the case that both polygons are rectilinear, we present a dynamic programming approach that yields such a tight hull in polynomial time. For arbitrary simple polygons we can use the same approach to obtain approximate tight rectilinear hulls.

Abstract: We study the following problems: Given a triangle or parallelogram, how many unit-disks can be packed nonoverlappingly into it? It is not known whether these problems are NP-hard or in NP. We give first results on their approximability and therefore a better understanding of their complexity. In the case that all inner angles are bounded from below by a constant, we give a PTAS for each problem. For the case of arbitrarily small inner angles, we give an algorithm with constant-factor approximation and polynomial running time for triangles.

Abstract: We prove that the number of unit distances among n planar points is at most 2.09n^4/3, improving on the previous best bound of 8n^4/3. We also improve the best known extremal values for n ≥ 25.