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