The planar tree packing theorem

Markus Geyer, Michael Hoffmann, Michael Kaufmann, Vincent Kusters & Csaba D Tóth
Packing graphs is a combinatorial problem where several given graphs are being mapped into a common host graph such that every edge is used at most once. In the planar tree packing problem we are given two trees $T_1$ and $T_2$ on $n$ vertices and have to find a planar graph on $n$ vertices that is the edge-disjoint union of $T_1$ and $T_2$. A clear exception that must be made is the star which cannot...

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...

Journal of Computational Geometry, Vol 9, No 1 (2018)

Journal Of Computational Geometry
Flat foldings of plane graphs with prescribed angles and edge lengths...74–93 On the geodesic centers of polygonal domains...131–190 Scalable exact visualization of isocontours in road networks via minimum-link paths...27–73 Computing maxmin edge length triangulations...1–26 Planar and poly-arc Lombardi drawings...328–355 Drawing planar graphs with many collinear vertices...94–130 Array-based compact data structures for triangulations: Practical solutions with theoretical guarantees...247–289 Improved time-space trade-offs for computing Voronoi diagrams...191–212 Topological drawings of complete bipartite graphs...213–246 Thickness and antithickness of graphs...356–386...

Weighted geometric set multi-cover via quasi-uniform sampling

Nikhil Bansal & Kirk Pruhs
We give a randomized polynomial time algorithm with approximation ratio $O(\log \phi(n))$ for weighted set multi-cover instances with a shallow cell complexity of at most $f(z,k) =z\phi(z) k^{O(1)}$. Up to constant factors, this matches a recent result of Chan, Grant, Konemann and Sharpe for the set cover case, i.e. when all the covering requirements are 1. One consequence of this is an $O(1)$-approximation for geometric weighted set multi-cover problems when the geometric objects have linear...

Improved time-space trade-offs for computing Voronoi diagrams

Bahareh Banyassady, Matias Korman, Wolfgang Mulzer, André Van Renssen, Marcel Roeloffzen, Paul Seiferth & Yannik Stein
Let $P$ be a planar set of $n$ sites in general position. For $k \in \{1, \dots, n-1\}$, the Voronoi diagram of order $k$ for $P$ is obtained by subdividing the plane into cells such that points in the same cell have the same set of nearest $k$ neighbors in $P$. The (nearest site) Voronoi diagram (NVD) and the farthest site Voronoi diagram (FVD) are the particular cases of $k=1$ and $k=n-1$, respectively. For any...

Colouring the triangles determined by a point set

Ruy Fabila-Monroy & David R. Wood
Let P be a set of n points in general position in the plane. We study the chromatic number of the intersection graph of the open triangles determined by P. It is known that this chromatic number is at least n3/27+O(n2) and, if P is in convex position, the answer is n3/24+O(n2). We prove that for arbitrary P, the chromatic number is at most n3/19.259+O(n2).

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...

Making triangles colorful

Jean Cardinal, Kolja Knauer, Piotr Micek & Torsten Ueckerdt
We prove that for any point set P in the plane, a triangle T, and a positive integer k, there exists a coloring of P with k colors such that any homothetic copy of T containing at least 144k8 points of P contains at least one of each color. This is the first polynomial bound for range spaces induced by homothetic polygons.The only previously known bound for this problem applies to the more general case...

Random hyperplane search trees in high dimensions

Luc Devroye & James King
Given a set S of n ≥ d points in general position in Rd, a random hyperplane split is obtained by sampling d points uniformly at random without replacement from S and splitting based on their affine hull. A random hyperplane search tree is a binary space partition tree obtained by recursive application of random hyperplane splits. We investigate the structural distributions of such random trees with a particular focus on the growth with d....

Computing maxmin edge length triangulations

Sándor P. Fekete, Winfried Hellmann, Michael Hemmer, Arne Schmidt & Julian Troegel
In 1991, Edelsbrunner and Tan gave an $O(n^2)$ algorithm for finding the MinMax Length triangulation of a set of points in the plane, but stated the complexity of finding a MaxMin Edge Length Triangulation (MELT) as a natural open problem. We resolve this long-standing problem by showing that computing a MELT is NP-complete. Moreover, we prove that (unless P=NP), there is no polynomial-time approximation algorithm that can approximate MELT within any polynomial factor. While this...

Journal of Computational Geometry, Vol 7, No 2 (2016): Special Issue of Selected Papers from SoCG 2015

Journal Of Computational Geometry
A special issue containing selected papers from the 31st International Symposium on Computational Geometry (SoCG 2015).

Which point sets admit a $k$-angulation?

Michael S. Payne, Jens M. Schmidt & David R. Wood
For $k\ge 3$, a $k$-angulation is a 2-connected plane graph in which every internal face is a $k$-gon. We say that a point set $P$ admits a plane graph $G$ if there is a straight-line drawing of $G$ that maps $V(G)$ onto $P$ and has the same facial cycles and outer face as $G$. We investigate the conditions under which a point set $P$ admits a $k$-angulation and find that, for sets containing at least...

Approximate Euclidean Ramsey theorems

According to a classical result of Szemerédi, every dense subset of 1,2,…,N contains an arbitrary long arithmetic progression, if N is large enough. Its analogue in higher dimensions due to Fürstenberg and Katznelson says that every dense subset of {1,2,…,N}d contains an arbitrary large grid, if N is large enough. Here we generalize these results for separated point sets on the line and respectively in the Euclidean space: (i) every dense separated set of points...

Drawing planar graphs with many collinear vertices

Giordano Da Lozzo, Vida Dujmović, Fabrizio Frati, Tamara Mchedlidze & Vincenzo Roselli
Consider the following problem: Given a planar graph $G$, what is the maximum number $p$ such that $G$ has a planar straight-line drawing with $p$ collinear vertices? This problem resides at the core of several graph drawing problems, including universal point subsets, untangling, and column planarity. The following results are known for it: Every $n$-vertex planar graph has a planar straight-line drawing with $\Omega(\sqrt{n})$ collinear vertices; for every $n$, there is an $n$-vertex planar graph...

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...

Recursive tilings and space-filling curves with little fragmentation

Herman Haverkort
This paper defines the Arrwwid number of a recursive tiling (or space-filling curve) as the smallest number a such that any ball Q can be covered by a tiles (or curve fragments) with total volume O(volume(Q)). Recursive tilings and space-filling curves with low Arrwwid numbers can be applied to optimize disk, memory or server access patterns when processing sets of points inRd. This paper presents recursive tilings and space-filling curves with optimal Arrwwid numbers. For...

Approximating the average stretch factor of geometric graphs

Siu-Wing Cheng, Christian Knauer, Stefan Langerman & Michiel Smid
Let G be a geometric graph whose vertex set S is a set of n points in ℝd. The stretch factor of two distinct points p and q in S is the ratio of their shortest-path distance in G and their Euclidean distance. We consider the problem of approximating the average of the n choose 2 stretch factors determined by all pairs of points in S. We show that for paths, cycles, and trees, this...

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....

2-manifold recognition is in logspace

Benjamin A Burton, Murray Elder, Arkadius Kalka & Stephan Tillmann
We prove that the homeomorphism problem for 2--manifolds can be decided in logspace. The proof relies on Reingold's logspace solution to the undirected $s,t$-connectivity problem in graphs.

Kinetic convex hulls, Delaunay triangulations and connectivity structures in the black-box model

Mark De Berg, Marcel Roeloffzen & Bettina Speckmann
Over the past decade, the kinetic-data-structures framework has become thestandard in computational geometry for dealing with moving objects. A fundamental assumption underlying the framework is that the motions of the objects are known in advance. This assumption severely limits the applicability of KDSs. We study KDSs in the black-box model, which is a hybrid of the KDS model and the traditional time-slicing approach. In this more practical model we receive the position of each object...

Central trajectories

Marc Van Kreveld, Maarten Löffler & Frank Staals

Minimax rates for estimating the dimension of a manifold

Jisu Kim, Alessandro Rinaldo & Larry Wasserman
Many algorithms in machine learning and computational geometry require, as input, the intrinsic dimension of the manifold that supports the probability distribution of the data. This parameter is rarely known and therefore has to be estimated. We characterize the statistical difficulty of this problem by deriving upper and lower bounds on the minimax rate for estimating the dimension. First, we consider the problem of testing the hypothesis that the support of the data-generating probability distribution...

On the complexity of minimum-link path problems

Irina Kostitsyna, Maarten Löffler, Valentin Polishchuk & Frank Staals
We revisit the minimum-link path problem: Given a polyhedral domain and two points in it, connect the points by a polygonal path with minimum number of edges. We consider settings where the vertices and/or the edges of the path are restricted to lie on the boundary of the domain, or can be in its interior. Our results include bit complexity bounds, a novel general hardness construction, and a polynomial-time approximation scheme. We fully characterize the...

Guest editors' foreword

Sándor P. Fekete & Anna Lubiw
Guest Editor's Foreword for the SoCG 2016 Special Issue.

Recursively-regular subdivisions and applications

Rafel Jaume & Günter Rote
We generalize regular subdivisions (polyhedral complexes resulting from the projection of the lower faces of a polyhedron) introducing the class of recursively-regular subdivisions. Informally speaking, a recursively-regular subdivision is a subdivision that can be obtained by splitting some faces of a regular subdivision by other regular subdivisions (and continue recursively). We also define the finest regular coarsening and the regularity tree of a polyhedral complex. We prove that recursively-regular subdivisions are not necessarily connected by...

• 2016
113
• 2017
22
• 2018
22
• 2019
6

• Text
162