169 Works

Simplices modelled on spaces of constant curvature

Ramsay Dyer, Gert Vegter & Mathijs Hubertus Maria Johannes Wintraecken
We give non-degeneracy criteria for Riemannian simplices based on simplices in spaces of constant sectional curvature. It extends previous work (SoCG15) on Riemannian simplices, where we developed Riemannian simplices with respect to Euclidean reference simplices. The criteria we give in this article are in terms of quality measures for spaces of constant curvature that we develop here. We see that simplices in spaces that have nearly constant curvature, are already non-degenerate under very weak quality...

Covering Many Points with a Small-Area Box

Mark De Berg, Sergio Cabello, Otfried Cheong, David Eppstein & Christian Knauer
Let $P$ be a set of $n$ points in the plane. We show how to find, for a given integer $k>0$, the smallest-area axis-parallel rectangle that covers $k$ points of $P$ in $O(nk^2 \log n+ n\log^2 n)$ time. We also consider the problem of, given a value $\alpha>0$, covering as many points of $P$ as possible with an axis-parallel rectangle of area at most $\alpha$. For this problem we give a probabilistic $(1-\varepsilon)$-approximation that works...

Pattern overlap implies runaway growth in hierarchical tile systems

David Doty, Ho-Lin Chen, Jan Manuch, Arash Rafiey & Ladislav Stacho
We show that in the hierarchical tile assembly model, if there is a producible assembly that overlaps a nontrivial translation of itself consistently (i.e., the pattern of tile types in the overlap region is identical in both translations), then arbitrarily large assemblies are producible. The significance of this result is that tile systems intended to controllably produce finite structures must avoid pattern repetition in their producible assemblies that would lead to such overlap. This answers...

A new drawing for simple Venn diagrams based on algebraic construction

Arnaud Bannier & Nicolas Bodin
Venn diagrams are used to display all relations between a finite number of sets. Recent researches in this domain concern the mathematical aspects of these constructions, but are not directed towards the readability of the diagram. This article presents a new way to draw easy-to-read Venn diagrams, in which each region tends to be drawn with the same size when the number of sets grows, and tends to draw a grid. Finally, using linear algebra,...

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

The worst visibility walk in a random Delaunay triangulation is $O(\sqrt{n})$

Olivier Devillers & Ross Hemsley
We show that the memoryless routing algorithms Greedy Walk, Compass Walk, and all variants of visibility walk based on orientation predicates are asymptotically optimal in the average case on the Delaunay triangulation. More specifically, we consider the Delaunay triangulation of an unbounded Poisson point process of unit rate and demonstrate that, for any pair of vertices $(s,t)$ inside $[0,n]^2$, the ratio between the longest and shortest visibility walks between $s$ and $t$ is bounded by...

On a conjecture of Lovász on circle-representations of simple 4-regular planar graphs

Michael A Bekos & Chrysanthi N Raftopoulou
Lovász conjectured that every connected 4-regular planar graph $G$ admits a realization as a system of circles, i.e., it can be drawn on the plane utilizing a set of circles, such that the vertices of $G$ correspond to the intersection and touching points of the circles and the edges of $G$ are the arc segments among pairs of intersection and touching points of the circles. In this paper, we settle this conjecture. In particular, (a)...

On isolating points using unit disks

Matt Gibson, Gaurav Kanade, Rainer Penninger, Kasturi Varadarajan & Ivo Vigan
Given a set of points in the plane and a set of disks (that we think of as wireless sensors) which separate the points, we consider the problem of selecting a minimum subset of the disks such that any path between any pair of points is intersected by at least one of the selected disks. We present a $(9 + \epsilon)$-approximation algorithm for this problem and show that it is NP-complete even if all disks...

Simplicial flat norm with scale

Sharif Ibrahim, Bala Krishnamoorthy & Kevin Vixie
We study the multiscale simplicial flat norm (MSFN) problem, which computes flat norm at various scales of sets defined as oriented subcomplexes of finite simplicial complexes in arbitrary dimensions. We show that MSFN is NP-complete when homology is defined over integers. We cast MSFN as an instance of integer linear optimization. Following recent results on related problems, the MSFN integer program can be solved in polynomial time by solving its linear programming relaxation, when the...

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

Guarding terrains via local search

Erik Krohn, Matt Gibson, Gaurav Kanade & Kasturi Varadarajan
We obtain a polynomial time approximation scheme for the terrain guarding problem improving upon several recent constant factor approximations. Our algorithm is a local search algorithm inspired by the recent results of Chan and Har-Peled (SoCG 2009) and Mustafa and Ray (DCG 2010). Our key contribution is to show the existence of a planar graph that appropriately relates the local and global optimum.

Topological drawings of complete bipartite graphs

Jean Cardinal & Stefan Felsner
Topological drawings are natural representations of graphs in the plane, where vertices are represented by points, and edges by curves connecting the points. Topological drawings of complete graphs and of complete bipartite graphs have been studied extensively in the context of crossing number problems. We consider a natural class of simple topological drawings of {\em complete bipartite} graphs, in which we require that one side of the vertex set bipartition lies on the outer boundary...

$d$-representability of simplicial complexes of fixed dimension

Martin Tancer
Let K be a simplicial complex with vertex set V = v1,…,vn. The complex K is d-representable if there is a collection {C1,…,Cn} of convex sets in Rd such that a subcollection {Ci1,…,Cij} has a nonempty intersection if and only if {vi1,…,vij} is a face of K. In 1967 Wegner proved that every simplicial complex of dimension d is (2d+1)-representable. He also conjectured that his bound is the best possible, i.e., that there are d-dimensional...

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

Incidences with $k$-non-degenerate sets and their applications

Abdul Basit & Adam Sheffer
We study point-sphere and point-plane incidences in the three-dimensional space. In particular, for $1 < k < n$, we say that a set of spheres (resp., of planes) is $k$-non-degenerate if no circle is contained in $k$ spheres of the set (resp., if no line is contained in $k$ planes of the set). We prove that, for every $\varepsilon>0$, the number of incidences between a set of $m$ points and a $k$-non-degenerate set of $n$...

On the structure of Schnyder woods on orientable surfaces

Kolja Knauer, Daniel Gonçalves & Benjamin Leveque
We propose a simple generalization of Schnyder woods from the plane to maps on orientable surfaces of higher genus. This is done in the language of angle labelings. Generalizing results of de Fraysseix and Ossona de Mendez, and Felsner, we establish a correspondence between these labelings and orientations and characterize the set of orientations of a map that correspond to such a Schnyder labeling. Furthermore, we study the set of these orientations of a given...

Ptolemaic indexing

Magnus Lie Hetland
This paper discusses a new family of bounds for use in similarity search, related to those used in metric indexing, but based on Ptolemy's inequality, rather than the metric axioms. Ptolemy's inequality holds for the well-known Euclidean distance, but is also shown here to hold for quadratic form metrics in general, with Mahalanobis distance as an important special case. The inequality is examined empirically on both synthetic and real-world data sets and is also found...

On visibility and blockers

Attila Pór & David R. Wood
This expository paper discusses some conjectures related to visibility and blockers for sets of points in the plane.

Shortest path to a segment and quickest visibility queries

Esther M Arkin, Alon Efrat, Christian Knauer, Joseph SB Mitchell, Valentin Polishchuk, Günter Rote, Lena Schlipf & Topi Talvitie
We show how to preprocess a polygonal domain with a fixed starting point $s$ in order to answer efficiently the following queries: Given a point $q$, how should one move from $s$ in order to see $q$ as soon as possible? This query resembles the well-known shortest-path-to-a-point query, except that the latter asks for the fastest way to reach $q$, instead of seeing it. Our solution methods include a data structure for a different generalization...

Happy endings for flip graphs

David Eppstein
We show that the triangulations of a finite point set form a flip graph that can be embedded isometrically into a hypercube, if and only if the point set has no empty convex pentagon. Point sets with no empty pentagon include intersections of lattices with convex sets, points on two lines, and several other infinite families. As a consequence, flip distance in such point sets can be computed efficiently.

Scalable exact visualization of isocontours in road networks via minimum-link paths

Moritz Baum, Thomas Bläsius, Andreas Gemsa, Ignaz Rutter & Franziska Wegner
Isocontours in road networks represent the area that is reachable from a source within a given resource limit. We study the problem of computing accurate isocontours in realistic, large-scale networks. We propose isocontours represented by polygons with minimum number of segments that separate reachable and unreachable components of the network. Since the resulting problem is not known to be solvable in polynomial time, we introduce several heuristics that run in (almost) linear time and are...

Computing multidimensional persistence

Gunnar Carlsson, Gurjeet Singh & Afra J. Zomorodian
The theory of multidimensional persistence captures the topology of a multifiltration - a multiparameter family of increasing spaces. Multifiltrations arise naturally in the topological analysis of scientific data. In this paper, we give a polynomial time algorithm for computing multidimensional persistence. We recast this computation as a problem within computational commutative algebra and utilize algorithms from this area to solve it. While the resulting problem is EXPSPACE-complete and the standard algorithms take doubly-exponential time, we...

Journal of Computational Geometry, Vol 4, No 1 (2013)

Journal Of Computational Geometry
Worst-case and smoothed analysis of k-means clustering with Bregman divergences...94–132 Metric inequalities for polygons...79–93 On affine rigidity...160–181 Fat polygonal partitions with applications to visualization and embeddings...212–239 Flow computations on imprecise terrains...38–78 Simplicial flat norm with scale...133–159 The number of distinct distances from a vertex of a convex polygon...1–12 Embedding the dual complex of hyper-rectangular partitions...13–37 Network farthest-point diagrams...182–211 Making triangles colorful...240–246

Worst-case and smoothed analysis of k-means clustering with Bregman divergences

Bodo Manthey & Heiko Roeglin
The k-means method is the method of choice for clustering large-scale data sets and it performs exceedingly well in practice despite its exponential worst-case running-time. To narrow the gap between theory and practice, k-means has been studied in the semi-random input model of smoothed analysis, which often leads to more realistic conclusions than mere worst-case analysis. For the case that n data points in Rd are perturbed by Gaussian noise with standard deviation σ, it...

A plane 1.88-spanner for points in convex position

Ahmad Biniaz, Mahdi Amani, Anil Maheshwari, Michiel Smid, Prosenjit Bose & Jean-Lou De Carufel
Let $S$ be a set of $n$ points in the plane that is in convex position. For a real number $t>1$, we say that a point $p$ in $S$ is $t$-good if for every point $q$ of $S$, the shortest-path distance between $p$ and $q$ along the boundary of the convex hull of $S$ is at most $t$ times the Euclidean distance between $p$ and $q$. We prove that any point that is part of...

Registration Year

  • 2016
  • 2017
  • 2018
  • 2019

Resource Types

  • Text