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><p>JoCG is a member of the <a href="http://freejournals.org/">Free Journal Network</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)Tue, 27 Feb 2018 00:00:00 -0500OJS 2.4.5.0http://blogs.law.harvard.edu/tech/rss60Computing maxmin edge length triangulations
http://jocg.org/index.php/jocg/article/view/319
<div class="page" title="Page 1"><div class="layoutArea"><div class="column">In 1991, Edelsbrunner and Tan gave an $O(n^2)$ algorithm for finding the MinMax Length triangulation of a set of points in the plane, but stated the complexity of finding a MaxMin Edge Length Triangulation (MELT) as a natural open problem. We resolve this long-standing problem by showing that computing a MELT is NP-complete. Moreover, we prove that (unless P=NP), there is no polynomial-time approximation algorithm that can approximate MELT within any polynomial factor. </div><div class="column"> </div><div class="column">While this may be taken as conclusive evidence from a theoretical point of view that the problem is hopelessly intractable, it still makes sense to consider powerful optimization methods, such as integer programming (IP), in order to obtain provably optimal solutions for intances of non-trivial size. A straightforward IP based on pairwise disjointness of the $\Theta(n^2)$ segments between the n points has $\Theta(n^4)$ constraints, making this IP hopelessly intractable from a practical point of view, even for relatively small $n$. The main algorithm engineering twist of this paper is to demonstrate how the combination of geometric insights with refined methods of combinatorial optimization can still help to put together an exact method capable of computing optimal MELT solutions for planar point sets up to $n = 200$. Our key idea is to exploit specific geometric properties in combination with more compact IP formulations, such that we are able to drastically reduce the IPs. On the practical side, we combine two of the most powerful software packages for the individual components: CGAL for carrying out the geometric computations, and CPLEX for solving the IPs. In addition, we discuss specific analytic aspects of the speedup for random point sets. </div></div></div>Sándor P. Fekete, Winfried Hellmann, Michael Hemmer, Arne Schmidt, Julian Troegelhttp://jocg.org/index.php/jocg/article/view/319Tue, 27 Feb 2018 21:51:29 -0500Scalable exact visualization of isocontours in road networks via minimum-link paths
http://jocg.org/index.php/jocg/article/view/313
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 simple enough to be implemented in practice. A key ingredient is a new practical linear-time algorithm for minimum-link paths in simple polygons. Experiments in a challenging realistic setting show excellent performance of our algorithms in practice, computing near-optimal solutions in a few milliseconds on average, even for long ranges.Moritz Baum, Thomas Bläsius, Andreas Gemsa, Ignaz Rutter, Franziska Wegnerhttp://jocg.org/index.php/jocg/article/view/313Tue, 27 Feb 2018 21:56:56 -0500Flat foldings of plane graphs with prescribed angles and edge lengths
http://jocg.org/index.php/jocg/article/view/191
<p>When can a plane graph with prescribed edge lengths and prescribed angles (from among $\{0,180^\circ,<br />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 vertex should sum to $360^\circ$, and every face of the graph must itself be flat foldable. This characterization leads to a linear-time algorithm for testing flat foldability of plane graphs with prescribed edge lengths and angles, and a polynomial-time algorithm for counting the number of distinct folded states.</p>Zachary Abel, Erik D. Demaine, Martin L. Demaine, David Eppstein, Anna Lubiw, Ryuhei Ueharahttp://jocg.org/index.php/jocg/article/view/191Tue, 27 Feb 2018 22:03:55 -0500Drawing planar graphs with many collinear vertices
http://jocg.org/index.php/jocg/article/view/326
<p>Consider the following problem: Given a planar graph $G$, what is the maximum number $p$ such that $G$ has a planar straight-line drawing with $p$ collinear vertices? This problem resides at the core of several graph drawing problems, including universal point subsets, untangling, and column planarity. The following results are known for it: Every $n$-vertex planar graph has a planar straight-line drawing with $\Omega(\sqrt{n})$ collinear vertices; for every $n$, there is an $n$-vertex planar graph whose every planar straight-line drawing has $O(n^\sigma)$ collinear vertices, where $\sigma<0.986$; every $n$-vertex planar graph of treewidth at most two has a planar straight-line drawing with $\Theta(n)$ collinear vertices. We extend the linear bound to planar graphs of treewidth at most three and to triconnected cubic planar graphs. This (partially) answers two open problems posed by Ravsky and Verbitsky [WG 2011:295<span>–</span>306]. Similar results are not possible for all bounded-treewidth planar graphs or for all bounded-degree planar graphs. For planar graphs of treewidth at most three, our results also imply asymptotically tight bounds for all of the other above mentioned graph drawing problems.</p>Giordano Da Lozzo, Vida Dujmović, Fabrizio Frati, Tamara Mchedlidze, Vincenzo Rosellihttp://jocg.org/index.php/jocg/article/view/326Thu, 03 May 2018 09:30:38 -0400