### 6,105 Works

### Star Unfolding of Boxes (Multimedia Exposition)

Dani Demas, Satyan L. Devadoss & Yu Xuan Hong
Given a convex polyhedron, the star unfolding of its surface is obtained by cutting along the shortest paths from a fixed source point to each of its vertices. We present an interactive application that visualizes the star unfolding of a box, such that its dimensions and source point locations can be continuously toggled by the user.

### VoroCrust Illustrated: Theory and Challenges (Multimedia Exposition)

Ahmed Abdelkader, Chandrajit L. Bajaj, Mohamed S. Ebeida, Ahmed H. Mahmoud, Scott A. Mitchell, John D. Owens & Ahmad A. Rushdi
Over the past decade, polyhedral meshing has been gaining popularity as a better alternative to tetrahedral meshing in certain applications. Within the class of polyhedral elements, Voronoi cells are particularly attractive thanks to their special geometric structure. What has been missing so far is a Voronoi mesher that is sufficiently robust to run automatically on complex models. In this video, we illustrate the main ideas behind the VoroCrust algorithm, highlighting both the theoretical guarantees and...

### Coordinated Motion Planning: The Video (Multimedia Exposition)

Aaron T. Becker, Sándor P. Fekete, Phillip Keldenich, Matthias Konitzny, Lillian Lin & Christian Scheffer
We motivate, visualize and demonstrate recent work for minimizing the total execution time of a coordinated, parallel motion plan for a swarm of N robots in the absence of obstacles. Under relatively mild assumptions on the separability of robots, the algorithm achieves constant stretch: If all robots want to move at most d units from their respective starting positions, then the total duration of the overall schedule (and hence the distance traveled by each robot)...

### Geometric Realizations of the 3D Associahedron (Multimedia Exposition)

Satyan L. Devadoss, Daniel D. Johnson, Justin Lee & Jackson Warley
The associahedron is a convex polytope whose 1-skeleton is isomorphic to the flip graph of a convex polygon. There exists an elegant geometric realization of the associahedron, using the remarkable theory of secondary polytopes, based on the geometry of the underlying polygon. We present an interactive application that visualizes this correspondence in the 3D case.

### An O(n log n)-Time Algorithm for the k-Center Problem in Trees

Haitao Wang & Jingru Zhang
We consider a classical k-center problem in trees. Let T be a tree of n vertices and every vertex has a nonnegative weight. The problem is to find k centers on the edges of T such that the maximum weighted distance from all vertices to their closest centers is minimized. Megiddo and Tamir (SIAM J. Comput., 1983) gave an algorithm that can solve the problem in O(n log^2 n) time by using Cole's parametric search....

### New Bounds for Range Closest-Pair Problems

Jie Xue, Yuan Li, Saladi Rahul & Ravi Janardan
Given a dataset S of points in R^2, the range closest-pair (RCP) problem aims to preprocess S into a data structure such that when a query range X is specified, the closest-pair in S cap X can be reported efficiently. The RCP problem can be viewed as a range-search version of the classical closest-pair problem, and finds applications in many areas. Due to its non-decomposability, the RCP problem is much more challenging than many traditional...

### Fractal Dimension and Lower Bounds for Geometric Problems

Anastasios Sidiropoulos, Kritika Singhal & Vijay Sridhar
We study the complexity of geometric problems on spaces of low fractal dimension. It was recently shown by [Sidiropoulos & Sridhar, SoCG 2017] that several problems admit improved solutions when the input is a pointset in Euclidean space with fractal dimension smaller than the ambient dimension. In this paper we prove nearly-matching lower bounds, thus establishing nearly-optimal bounds for various problems as a function of the fractal dimension.
More specifically, we show that for any...

### The Trisection Genus of Standard Simply Connected PL 4-Manifolds

Jonathan Spreer & Stephan Tillmann
Gay and Kirby recently introduced the concept of a trisection for arbitrary smooth, oriented closed 4-manifolds, and with it a new topological invariant, called the trisection genus. In this note we show that the K3 surface has trisection genus 22. This implies that the trisection genus of all standard simply connected PL 4-manifolds is known. We show that the trisection genus of each of these manifolds is realised by a trisection that is supported by...

### Almost All String Graphs are Intersection Graphs of Plane Convex Sets

János Pach, Bruce Reed & Yelena Yuditsky
A string graph is the intersection graph of a family of continuous arcs in the plane. The intersection graph of a family of plane convex sets is a string graph, but not all string graphs can be obtained in this way. We prove the following structure theorem conjectured by Janson and Uzzell: The vertex set of almost all string graphs on n vertices can be partitioned into five cliques such that some pair of them...

### An Improved Bound for the Size of the Set A/A+A

Oliver Roche-Newton
It is established that for any finite set of positive real numbers A, we have |A/A+A| >> |A|^{3/2+1/26} / log^{5/6}|A|.

### Near-Optimal Coresets of Kernel Density Estimates

Jeff M. Phillips & Wai Ming Tai
We construct near-optimal coresets for kernel density estimate for points in R^d when the kernel is positive definite. Specifically we show a polynomial time construction for a coreset of size O(sqrt{d log (1/epsilon)}/epsilon), and we show a near-matching lower bound of size Omega(sqrt{d}/epsilon). The upper bound is a polynomial in 1/epsilon improvement when d in [3,1/epsilon^2) (for all kernels except the Gaussian kernel which had a previous upper bound of O((1/epsilon) log^d (1/epsilon))) and the...

### Optimal Analysis of an Online Algorithm for the Bipartite Matching Problem on a Line

Sharath Raghvendra
In the online metric bipartite matching problem, we are given a set S of server locations in a metric space. Requests arrive one at a time, and on its arrival, we need to immediately and irrevocably match it to a server at a cost which is equal to the distance between these locations. A alpha-competitive algorithm will assign requests to servers so that the total cost is at most alpha times the cost of M_{Opt}...

### Edge-Unfolding Nearly Flat Convex Caps

Joseph O'Rourke
The main result of this paper is a proof that a nearly flat, acutely triangulated convex cap C in R^3 has an edge-unfolding to a non-overlapping polygon in the plane. A convex cap is the intersection of the surface of a convex polyhedron and a halfspace. "Nearly flat" means that every outer face normal forms a sufficiently small angle f < F with the z^-axis orthogonal to the halfspace bounding plane. The size of F...

### A Crossing Lemma for Multigraphs

János Pach & Géza Tóth
Let G be a drawing of a graph with n vertices and e>4n edges, in which no two adjacent edges cross and any pair of independent edges cross at most once. According to the celebrated Crossing Lemma of Ajtai, Chvátal, Newborn, Szemerédi and Leighton, the number of crossings in G is at least c{e^3 over n^2}, for a suitable constant c>0. In a seminal paper, Székely generalized this result to multigraphs, establishing the lower bound...

### Approximate Range Queries for Clustering

Eunjin Oh & Hee-Kap Ahn
We study the approximate range searching for three variants of the clustering problem with a set P of n points in d-dimensional Euclidean space and axis-parallel rectangular range queries: the k-median, k-means, and k-center range-clustering query problems. We present data structures and query algorithms that compute (1+epsilon)-approximations to the optimal clusterings of P cap Q efficiently for a query consisting of an orthogonal range Q, an integer k, and a value epsilon>0.

### Point Location in Dynamic Planar Subdivisions

Eunjin Oh & Hee-Kap Ahn
We study the point location problem on dynamic planar subdivisions that allows insertions and deletions of edges. In our problem, the underlying graph of a subdivision is not necessarily connected. We present a data structure of linear size for such a dynamic planar subdivision that supports sublinear-time update and polylogarithmic-time query. Precisely, the amortized update time is O(sqrt{n}log n(log log n)^{3/2}) and the query time is O(log n(log log n)^2), where n is the number...

### Random Walks on Polytopes of Constant Corank

Malte Milatz
We show that the pivoting process associated with one line and n points in r-dimensional space may need Omega(log^r n) steps in expectation as n -> infty. The only cases for which the bound was known previously were for r <= 3. Our lower bound is also valid for the expected number of pivoting steps in the following applications: (1) The Random-Edge simplex algorithm on linear programs with n constraints in d = n-r variables;...

### Table Based Detection of Degenerate Predicates in Free Space Construction

Victor Milenkovic, Elisha Sacks & Nabeel Butt
The key to a robust and efficient implementation of a computational geometry algorithm is an efficient algorithm for detecting degenerate predicates. We study degeneracy detection in constructing the free space of a polyhedron that rotates around a fixed axis and translates freely relative to another polyhedron. The structure of the free space is determined by the signs of univariate polynomials, called angle polynomials, whose coefficients are polynomials in the coordinates of the vertices of the...

### A Nearly Optimal Algorithm for the Geodesic Voronoi Diagram of Points in a Simple Polygon

Chih-Hung Liu
The geodesic Voronoi diagram of m point sites inside a simple polygon of n vertices is a subdivision of the polygon into m cells, one to each site, such that all points in a cell share the same nearest site under the geodesic distance. The best known lower bound for the construction time is Omega(n+m log m), and a matching upper bound is a long-standing open question. The state-of-the-art construction algorithms achieve O((n+m)log (n+m)) and...

### Further Consequences of the Colorful Helly Hypothesis

Leonardo Martínez-Sandoval, Edgardo Roldán-Pensado & Natan Rubin
Let F be a family of convex sets in R^d, which are colored with d+1 colors. We say that F satisfies the Colorful Helly Property if every rainbow selection of d+1 sets, one set from each color class, has a non-empty common intersection. The Colorful Helly Theorem of Lovász states that for any such colorful family F there is a color class F_i subset F, for 1 <= i <= d+1, whose sets have a...

### On Optimal Polyline Simplification Using the Hausdorff and Fréchet Distance

Marc Van Kreveld, Maarten Löffler & Lionov Wiratma
We revisit the classical polygonal line simplification problem and study it using the Hausdorff distance and Fréchet distance. Interestingly, no previous authors studied line simplification under these measures in its pure form, namely: for a given epsilon>0, choose a minimum size subsequence of the vertices of the input such that the Hausdorff or Fréchet distance between the input and output polylines is at most epsilon.
We analyze how the well-known Douglas-Peucker and Imai-Iri simplification algorithms...

### Graph-Based Time-Space Trade-Offs for Approximate Near Neighbors

Thijs Laarhoven
We take a first step towards a rigorous asymptotic analysis of graph-based methods for finding (approximate) nearest neighbors in high-dimensional spaces, by analyzing the complexity of randomized greedy walks on the approximate nearest neighbor graph. For random data sets of size n = 2^{o(d)} on the d-dimensional Euclidean unit sphere, using near neighbor graphs we can provably solve the approximate nearest neighbor problem with approximation factor c > 1 in query time n^{rho_{q} + o(1)}...

### An Optimal Algorithm to Compute the Inverse Beacon Attraction Region

Irina Kostitsyna, Bahram Kouhestani, Stefan Langerman & David Rappaport
The beacon model is a recent paradigm for guiding the trajectory of messages or small robotic agents in complex environments. A beacon is a fixed point with an attraction pull that can move points within a given polygon. Points move greedily towards a beacon: if unobstructed, they move along a straight line to the beacon, and otherwise they slide on the edges of the polygon. The Euclidean distance from a moving point to a beacon...

### Minimizing Crossings in Constrained Two-Sided Circular Graph Layouts

Fabian Klute & Martin Nöllenburg
Circular layouts are a popular graph drawing style, where vertices are placed on a circle and edges are drawn as straight chords. Crossing minimization in circular layouts is NP-hard. One way to allow for fewer crossings in practice are two-sided layouts that draw some edges as curves in the exterior of the circle. In fact, one- and two-sided circular layouts are equivalent to one-page and two-page book drawings, i.e., graph layouts with all vertices placed...

### Discrete Stratified Morse Theory: A User's Guide

Kevin Knudson & Bei Wang
Inspired by the works of Forman on discrete Morse theory, which is a combinatorial adaptation to cell complexes of classical Morse theory on manifolds, we introduce a discrete analogue of the stratified Morse theory of Goresky and MacPherson. We describe the basics of this theory and prove fundamental theorems relating the topology of a general simplicial complex with the critical simplices of a discrete stratified Morse function on the complex. We also provide an algorithm...