175 Works

Weighted geometric set cover problems revisited

Sariel Har-Peled & Mira Lee
We study several set cover problems in low dimensional geometric settings. Specifically, we describe a PTAS for the problem of computing a minimum cover of given points by a set of weighted fat objects. Here, we allow the objects to expand by some prespecified δ-fraction of their diameter. Next, we show that the problem of computing a minimum weight cover of points by weighted halfplanes (without expansion) can be solved exactly in the plane. We...

Sampling with removal in LP-type problems

Bernd Gärtner
Random sampling is an important tool in optimization subject to finitely or infinitely many constraints. Here we are interested in obtaining solutions of low cost that violate only few constraints. Under convexity or similar favorable conditions, and assuming fixed dimension, one can indeed derive combinatorial bounds on the expected number (or probability mass) of constraints violated by the optimal solution subject to a (small) random sample of constraints. The cost of the sample solution, however,...

The Hausdorff core problem on simple polygons

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

Time-space trade-offs for triangulating a simple polygon

Boris Aronov, Matias Korman, Simon Pratt, André Van Renssen & Marcel Roeloffzen
An $s$-workspace algorithm is an algorithm that has read-only access to the values of the input, write-only access to the output, and only uses $O(s)$ additional words of space. We present a randomized $s$-workspace algorithm for triangulating a simple polygon $P$ of $n$ vertices that runs in $O(n^2/s+n \log n \log^{5} (n/s))$ expected time using $O(s)$ variables, for any $s \leq n$. In particular, when $s \leq \frac{n}{\log n\log^{5}\log n}$ the algorithm runs in $O(n^2/s)$...

Minimum cycle and homology bases of surface-embedded graphs

Glencora Borradaile, Erin Wolf Chambers, Kyle Fox & Amir Nayyeri
We study the problems of finding a minimum cycle basis (a minimum-weight set of cycles that form a basis for the cycle space) and a minimum homology basis (a minimum-weight set of cycles that generates the 1-dimensional $(\mathbb{Z}_2)$-homology classes) of an undirected graph cellularly embedded on a surface. The problems are closely related, because the minimum cycle basis of a graph contains its minimum homology basis, and the minimum homology basis of the 1-skeleton of...

Journal of Computational Geometry, Vol 10, No 1 (2019)

Journal Of Computational Geometry
Minimax rates for estimating the dimension of a manifold...42–95 An abstract approach to polychromatic coloring: shallow hitting sets in ABA-free hypergraphs and pseudohalfplanes...1–26 All-Pairs Shortest Paths in Geometric Intersection Graphs...27–41

Partial covering of a circle by equal circles. Part I: The mechanical models

Zsolt Gáspár, Tibor Tarnai & Krisztián Hincz
How must n equal circles of given radius be placed so that they cover as great a part of the area of the unit circle as possible? To analyse this mathematical problem, mechanical models are introduced. A generalized tensegrity structure is associated with a maximum area configuration of the n circles, whose equilibrium configuration is determined numerically with the method of dynamic relaxation, and the stability of equilibrium is investigated by means of the stiffness...

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

Silhouette of a random polytope

Marc Glisse, Sylvain Lazard, Julien Michel & Marc Pouget
We consider random polytopes defined as the convex hull of a Poisson point process on a sphere in $\mathbb{R}^3$ such that its average number of points is $n$. We show that the expectation over all such random polytopes of the maximum size of their silhouettes viewed from infinity is $\Theta(\sqrt{n})$.

Towards plane spanners of degree 3

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

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

Hyperorthogonal well-folded Hilbert curves

Arie Bos & Herman Haverkort
R-trees can be used to store and query sets of point data in two or more dimensions. An easy way to construct and maintain R-trees for two-dimensional points, due to Kamel and Faloutsos, is to keep the points in the order in which they appear along the Hilbert curve. The R-tree will then store bounding boxes of points along contiguous sections of the curve, and the efficiency of the R-tree depends on the size of...

Cover contact graphs

Nieves Atienza, Natalia De Castro, Carmen Cortés, M. ÁNgeles Garrido, Clara I. Grima, Gregorio Hernández, Alberto Márquez, Auxiliadora Moreno-González, Martin Nöllenburg, José Ramon Portillo, Pedro Reyes, Jesús Valenzuela, Maria Trinidad Villar & Alexander Wolff
We study problems that arise in the context of covering certain geometric objects called seeds (e.g., points or disks) by a set of other geometric objects called cover (e.g., a set of disks or homothetic triangles). We insist that the interiors of the seeds and the cover elements are pairwise disjoint, respectively, but they can touch. We call the contact graph of a cover a cover contact graph (CCG). We are interested in three types...

On affine rigidity

Steven J. Gortler, Craig Gotsman, Ligang Liu & Dylan P. Thurston
We study the properties of affine rigidity of a hypergraph and prove a variety of fundamental results. First, we show that affine rigidity is a generic property (i.e., depends only on the hypergraph, not the particular embedding). Then we prove that a graph is generically neighborhood affinely rigid in d-dimensional space if it is (d+1)-vertex-connected. We also show neighborhood affine rigidity of a graph implies universal rigidity of its squared graph. Our results, and affine...

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

Flat foldings of plane graphs with prescribed angles and edge lengths

Zachary Abel, Erik D. Demaine, Martin L. Demaine, David Eppstein, Anna Lubiw & Ryuhei Uehara
When can a plane graph with prescribed edge lengths and prescribed angles (from among $\{0,180^\circ, 360^\circ\}$) be folded flat to lie in an infinitesimally thick line, without crossings? This problem generalizes the classic theory of single-vertex flat origami with prescribed mountain-valley assignment, which corresponds to the case of a cycle graph. We characterize such flat-foldable plane graphs by two obviously necessary but also sufficient conditions, proving a conjecture made in 2001: the angles at each...

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

Quasi-parallel segments and characterization of unique bichromatic matchings

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

Near-linear time medial axis approximation of smooth curves in $\mathbb{R}^3$

Christian Scheffer
We present the first algorithm to approximate the medial axis $M_{\gamma}$ of a smooth, closed curve $\gamma \subset \mathbb{R}^3$ in near-linear time. Our algorithm works on a sufficiently dense \eps-sample and comes with a convergence guarantee for the non-discrete, but continuous approximation object. As our approach also works correctly for a set of curves, we discuss the following application of the medial axis: The medial axis of two curves $\gamma_1$ and $\gamma_2$ can be applied...

Two-point L1 shortest path queries in the plane

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

The maximum number of faces of the Minkowski sum of three convex polytopes

Menelaos Karavelas, Christos Konaxis & Eleni Tzanaki
We derive tight expressions for the maximum number of $k$-faces, $0\le{}k\le{}d-1$, of the Minkowski sum, $P_1+P_2+P_3$, of three $d$-dimensional convex polytopes $P_1$, $P_2$ and $P_3$ in $\mathbb{R}^d$, as a function of the number of vertices of the polytopes, for any $d\ge{}2$. Expressing the Minkowski sum as a section of the Cayley polytope $\mathcal{C}$ of its summands, counting the $k$-faces of $P_1+P_2+P_3$ reduces to counting the $(k+2)$-faces of $\mathcal{C}$ that contain vertices from each of the...

Journal of Computational Geometry, Vol 1, No 1 (2010)

Journal Of Computational Geometry
On the stretch factor of convex Delaunay graphs...41–56 Computing the maximum detour of a plane geometric graph in subquadratic time...101–122 Visibility maps of realistic terrains have linear smoothed complexity...57–71 Computing multidimensional persistence...72–100 Welcome from the Editors-in-Chief...1–2 Happy endings for flip graphs...3–28 On visibility and blockers...29–40

Computing the maximum detour of a plane geometric graph in subquadratic time

Christian Wulff-Nilsen
Let G be a plane geometric graph where each edge is a line segment. We consider the problem of computing the maximum detour of G, defined as the maximum over all pairs of distinct points (vertices as well as interior points of edges) p and q of G of the ratio between the distance between p and q in G and the Euclidean distance ||pq||2. The fastest known algorithm for this problem has Θ(n2) running...

Embedding the dual complex of hyper-rectangular partitions

Michael Kerber
A rectangular partition is the partition of an (axis-aligned) rectangle into interior-disjoint rectangles. We ask whether a rectangular partition permits a nice drawing of its dual, that is, a straight-line embedding of it such that each dual vertex is placed into the rectangle that it represents. We show that deciding whether such a drawing exists is NP-complete. Moreover, we consider the drawing where a vertex is placed in the center of the representing rectangle and...

Forcing subarrangements in complete arrangements of pseudocircles

Ronald Ortner
In arrangements of pseudocircles (i.e., Jordan curves) the weight of a vertex (i.e., an intersection point) is the number of pseudocircles that contain the vertex in its interior. We show that in complete arrangements (in which each two pseudocircles intersect) $2n-1$ vertices of weight 0 force an $\alpha$-subarrangement, a certain arrangement of three pseudocircles. Similarly, $4n-5$ vertices of weight 0 force an $\alpha^4$-subarrangement (of four pseudocircles). These results on the one hand give improved bounds...

Registration Year

  • 2016
  • 2017
  • 2018
  • 2019

Resource Types

  • Text