Journal of Computational Geometry
http://www.jocg.org/index.php/jocg
The Journal of Computational Geometry (JoCG) is an international open access journal devoted to publishing original research of the highest quality in all aspects of computational geometry.<p>JoCG articles and supplementary data are freely available for download and JoCG charges no publishing fees of any kind.</p><p>All JoCG issues and articles are assigned a DOI. JoCG's data and content are safeguarded through <a href="/index.php/jocg/pages/view/backup">several backup mechanisms</a>.</p>en-USAuthors who publish with this journal agree to the following terms:<br /><br /><ol type="a"><ol type="a"><li>Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a <a href="http://creativecommons.org/licenses/by/3.0/" target="_new">Creative Commons Attribution License</a> that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.</li></ol></ol><br /><ol type="a"><ol type="a"><li>Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.</li></ol></ol><br /><ol type="a"><li>Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See <a href="http://opcit.eprints.org/oacitation-biblio.html" target="_new">The Effect of Open Access</a>).</li></ol>jocg@jocg.org (Managing Editors)morin@scs.carleton.ca (Pat Morin)Sat, 18 Feb 2017 14:31:30 -0500OJS 2.4.5.0http://blogs.law.harvard.edu/tech/rss60Approximating minimum-area rectangular and convex containers for packing convex polygons
http://www.jocg.org/index.php/jocg/article/view/289
We investigate the problem of finding a minimum-area container for the disjoint packing of a set of convex polygons by translations. In particular, we consider axis-parallel rectangles or arbitrary convex sets as containers. For both optimization problems which are NP-hard we develop efficient constant factor approximation algorithms.Helmut Alt, Mark de Berg, Christian Knauerhttp://www.jocg.org/index.php/jocg/article/view/289Sat, 18 Feb 2017 14:30:53 -0500Towards plane spanners of degree 3
http://www.jocg.org/index.php/jocg/article/view/295
<p>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$.</p><ol><li>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. </li><li>If $S$ is the vertex set of a non-uniform rectangular lattice, then we present an algorithm that constructs a plane $3\sqrt{2}$-spanner for $S$ whose vertex degree is at most 3. </li><li>If $S$ is in general position, then we show how to compute plane degree-3 spanners for $S$ with a linear number of Steiner points.</li></ol>Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Cyril Gavoille, Anil Maheshwari, Michiel Smidhttp://www.jocg.org/index.php/jocg/article/view/295Mon, 13 Mar 2017 11:48:39 -0400On interference among moving sensors and related problems
http://www.jocg.org/index.php/jocg/article/view/297
<p>We show that for any set of $n$ moving points in $\Re^d$ and any parameter $2 \le k \le n$, one can select a fixed non-empty subset of the points of size $O(k \log k)$, such that the Voronoi diagram of this subset is ``balanced'' at any given time (i.e., it contains $O(n/k)$ points per cell). We also show that the bound $O(k \log k)$ is near optimal even for the one dimensional case in which points move linearly in time. As an application, we show that one can assign communication radii to the sensors of a network of $n$ moving sensors so that at any given time, their interference is $O(\sqrt{n\log n})$. This is optimal up to an $O(\sqrt{\log n})$ factor. In order to obtain these results, we extend well-known results from $\varepsilon$-net theory to kinetic environments.</p>Jean-Lou De Carufel, Matthew J. Katz, Matias Korman, André van Renssen, Marcel Roeloffzen, Shakhar Smorodinskyhttp://www.jocg.org/index.php/jocg/article/view/297Tue, 25 Apr 2017 09:08:54 -0400Counting and enumerating crossing-free geometric graphs
http://www.jocg.org/index.php/jocg/article/view/280
<p>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.</p><p>The following results will emerge. The number of all crossing-free geometric graphs can be computed in time $O(c^nn^4)$ for some $c < 2.83929$. The number of crossing-free convex partitions can be computed in time $O(2^nn^4)$. The number of crossing-free perfect matchings can be computed in time $O(2^nn^4)$. The number of convex subdivisions can be computed in time $O(2^nn^4)$. The number of crossing-free spanning trees can be computed in time $O(c^nn^4)$ for some $c < 7.04313$. The number of crossing-free spanning cycles can be computed in time $O(c^nn^4)$ for some $c < 5.61804$.</p><p>Moreover, after a preprocessing phase with the same time bounds as above, we can enumerate the respective classes efficiently. For example, after $O(2^nn^4)$ time of preprocessing we can enumerate the set of all crossing-free perfect matchings using polynomial time per enumerated object. For crossing-free perfect matchings and convex partitions we further obtain enumeration algorithms where the time delay for each (in particular, the first) output is bounded by a polynomial in $n$.</p><p>All described algorithms are comparatively simple, both in terms of their analysis and implementation.</p>Manuel Wettsteinhttp://www.jocg.org/index.php/jocg/article/view/280Tue, 25 Apr 2017 09:51:07 -0400The projection median as a weighted average
http://www.jocg.org/index.php/jocg/article/view/244
The projection median of a set $P$ of $n$ points in $\mathbb{R}^d$ is a robust geometric generalization of the notion of univariate median to higher dimensions. In its original definition, the projection median is expressed as a normalized integral of the medians of the projections of $P$ onto all lines through the origin. We introduce a new definition in which the projection median is expressed as a weighted mean of $P$, and show the equivalence of the two definitions. In addition to providing a definition whose form is more consistent with those of traditional statistical estimators of location, this new definition for the projection median allows many of its geometric properties to be established more easily, as well as enabling new randomized algorithms that compute approximations of the projection median with increased accuracy and efficiency, reducing computation time from $O(n^{d+\epsilon})$ to $O(mnd)$, where $m$ denotes the number of random projections sampled. Selecting $m \in \Theta(\epsilon^{-2} d^2 \log n)$ or $m \in \Theta(\min ( d + \epsilon^{-2} \log n, \epsilon^{-2} n))$, suffices for our algorithms to return a point within relative distance $\epsilon$ of the true projection median with high probability, resulting in running times $O(d^3 n \log n)$ and $O(\min(d^2 n, d n^2))$ respectively, for any fixed $\epsilon$.Stephane Durocher, Alexandre Leblanc, Matthew Skalahttp://www.jocg.org/index.php/jocg/article/view/244Mon, 01 May 2017 13:30:31 -0400Time-space trade-offs for triangulating a simple polygon
http://www.jocg.org/index.php/jocg/article/view/307
<p>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)$ expected time.</p>Boris Aronov, Matias Korman, Simon Pratt, André van Renssen, Marcel Roeloffzenhttp://www.jocg.org/index.php/jocg/article/view/307Mon, 01 May 2017 13:32:08 -0400Competitive local routing with constraints
http://www.jocg.org/index.php/jocg/article/view/288
Let $P$ be a set of $n$ vertices in the plane and $S$ a set of non-crossing line segments between vertices in $P$, called constraints. Two vertices are visible if the straight line segment connecting them does not properly intersect any constraints. The constrained $\Theta_m$-graph is constructed by partitioning the plane around each vertex into $m$ disjoint cones, each with aperture $\theta = 2 \pi/m$, and adding an edge to the `closest' visible vertex in each cone. We consider how to route on the constrained $\Theta_6$-graph. We first show that no deterministic 1-local routing algorithm is $o(\sqrt{n})$-competitive on all pairs of vertices of the constrained $\Theta_6$-graph. After that, we show how to route between any two visible vertices of the constrained $\Theta_6$-graph using only 1-local information. Our routing algorithm guarantees that the returned path has length at most 2 times the Euclidean distance between the source and destination. Additionally, we provide a 1-local 18-competitive routing algorithm for visible vertices in the constrained half-$\Theta_6$-graph, a subgraph of the constrained $\Theta_6$-graph that is equivalent to the Delaunay graph where the empty region is an equilateral triangle. To the best of our knowledge, these are the first local routing algorithms in the constrained setting with guarantees on the length of the returned path.Prosenjit Bose, Rolf Fagerberg, André van Renssen, Sander Verdonschothttp://www.jocg.org/index.php/jocg/article/view/288Mon, 15 May 2017 06:44:12 -0400A new drawing for simple Venn diagrams based on algebraic construction
http://www.jocg.org/index.php/jocg/article/view/271
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, we prove that this construction gives a simple Venn diagram for any number of sets.Arnaud Bannier, Nicolas Bodinhttp://www.jocg.org/index.php/jocg/article/view/271Mon, 29 May 2017 10:02:04 -0400Classifying unavoidable Tverberg partitions
http://www.jocg.org/index.php/jocg/article/view/308
<div>Let $T(d,r) = (r-1)(d+1)+1$ be the parameter in Tverberg's theorem, and call a partition $\mathcal I$ of $\{1,2,\ldots,T(d,r)\}$ into $r$ parts a <em>Tverberg type</em>. We say that $\mathcal I$ o<em>ccurs</em> in an ordered point sequence $P$ if $P$ contains a subsequence $P'$ of $T(d,r)$ points such that the partition of $P'$ that is order-isomorphic to $\mathcal I$ is a Tverberg partition. We say that $\mathcal I$ is <em>unavoidable</em> if it occurs in every sufficiently long point sequence.<br /><br />In this paper we study the problem of determining which Tverberg types are unavoidable. We conjecture a complete characterization of the unavoidable Tverberg types, and we prove some cases of our conjecture for $d\le 4$. Along the way, we study the avoidability of many other geometric predicates.<br /><br />Our techniques also yield a large family of $T(d,r)$-point sets for which the number of Tverberg partitions is exactly $(r-1)!^d$. This lends further support for Sierksma's conjecture on the number of Tverberg partitions.</div><div> </div>Boris Bukh, Po-Shen Loh, Gabriel Nivaschhttp://www.jocg.org/index.php/jocg/article/view/308Tue, 04 Jul 2017 23:19:24 -0400How many three-dimensional Hilbert curves are there?
http://www.jocg.org/index.php/jocg/article/view/298
<p>Hilbert's two-dimensional space-filling curve is appreciated for its good locality-preserving properties and easy implementation for many applications. However, Hilbert did not describe how to generalize his construction to higher dimensions. In fact, the number of ways in which this may be done ranges from zero to infinite, depending on what properties of the Hilbert curve one considers to be essential.<br /><br />In this work we take the point of view that a Hilbert curve should at least be self-similar and traverse cubes octant by octant. We organize and explore the space of possible three-dimensional Hilbert curves and the potentially useful properties which they may have. We discuss a notation system that allows us to distinguish the curves from one another and enumerate them. This system has been implemented in a software prototype, available from the author's website.</p><p>Several examples of possible three-dimensional Hilbert curves are presented, including a curve that visits the points on most sides of the unit cube in the order of the two-dimensional Hilbert curve; curves of which not only the eight octants are similar to each other, but also the four quarters; a curve with excellent locality-preserving properties and endpoints that are not vertices of the cube; a curve in which all but two octants are each other's images with respect to reflections in axis-parallel planes; and curves that can be sketched on a grid without using vertical line segments. In addition, we discuss several four-dimensional Hilbert curves.<br /><br /></p>Herman Haverkorthttp://www.jocg.org/index.php/jocg/article/view/298Tue, 12 Sep 2017 09:15:34 -0400Qualitative symbolic perturbation: two applications of a new geometry-based perturbation framework
http://www.jocg.org/index.php/jocg/article/view/253
<br />In a classical <em>Symbolic Perturbation</em> scheme, degeneracies are handled by substituting some polynomials in $\varepsilon$ for the inputs of a predicate. Instead of a single perturbation, we propose to use a sequence of (simpler) perturbations. Moreover, we look at their effects geometrically instead of algebraically; this allows us to tackle cases that were not tractable with the classical algebraic approach.Olivier Devillers, Menelaos Karavelas, Monique Teillaudhttp://www.jocg.org/index.php/jocg/article/view/253Tue, 12 Sep 2017 13:59:48 -0400