Journal of Computational Geometry
http://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://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://jocg.org/index.php/jocg/article/view/289Sat, 18 Feb 2017 14:30:53 -0500Towards plane spanners of degree 3
http://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://jocg.org/index.php/jocg/article/view/295Mon, 13 Mar 2017 11:48:39 -0400On interference among moving sensors and related problems
http://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://jocg.org/index.php/jocg/article/view/297Tue, 25 Apr 2017 09:08:54 -0400Counting and enumerating crossing-free geometric graphs
http://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://jocg.org/index.php/jocg/article/view/280Tue, 25 Apr 2017 09:51:07 -0400