SoCG 2019: List of Accepted Papers

Adrian Dumitrescu. A Product Inequality for Extreme Distances
Sariel Har-Peled and Mitchell Jones. Journey to the Center of the Point Set
Xavier Goaoc, Andreas Holmsen and Cyril Nicaud. An experimental study of forbidden patterns in geometric permutations by combinatorial lifting
Shay Moran and Amir Yehudayoff. On weak ϵ-nets and the Radon number
Raphaël Tinarrage, Frederic Chazal, Marc Glisse, Hirokazu Anai, Yuichi Ike, Hiroya Inakoshi and Yuhei Umeda. DTM-based filtrations
Mozhgan Mirzaei and Andrew Suk. On grids in point-line arrangements in the plane
Janos Pach and Istvan Tomon. On the chromatic number of disjointness graphs of curves
Vladimir Braverman, Moses Charikar, William Kuszmaul, David P. Woodruff and Lin F. Yang. The One-Way Communication Complexity of Dynamic Time Warping Distance
Diego Ihara, Neshat Mohammadi and Anastasios Sidiropoulos. Algorithms for metric learning via contrastive embeddings
Pankaj K. Agarwal, Boris Aronov, Esther Ezra and Joshua Zahl. An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
Haitao Wang. A Divide-and-Conquer Algorithm for Two-Point L_1 Shortest Path Queries in Polygonal Domains
Akanksha Agrawal, Grzegorz Guspiel, Jayakrishnan Madathil, Saket Saurabh and Meirav Zehavi. Connecting the Dots (with Minimum Crossings)
Sándor Fekete, Phillip Keldenich and Christian Scheffer. Packing Disks into Disks with Optimal Worst-Case Density
Dominique Attali, Andre Lieutier and David Salinas. When convexity helps collapsing complexes
Luis Barba. Optimal algorithm for geodesic farthest-point Voronoi diagrams
Vida Dujmovic and Pat Morin. Dual Circumference and Collinear Sets
Timothy M. Chan and Sariel Har-Peled. Smallest k-Enclosing Rectangle Revisited
Chen Ziv and Micha Sharir. On the Complexity of the k-Level in Arrangements of Pseudoplanes
Yufei Tao and Yu Wang. Distribution-Sensitive Bounds on Relative Approximations of Geometric Ranges
Sergio Cabello and Timothy M. Chan. Computing Shapley values in the plane
Jean-Lou de Carufel, Adrian Dumitrescu, Wouter Meulemans, Tim Ophelders, Claire Pennarun, Csaba D. Tóth and Sander Verdonschot. Convex Polygons in Cartesian Products
Dror Aiger, Haim Kaplan, Efi Kokiopoulou, Micha Sharir and Bernhard Zeisl. General techniques for approximate incidences and their application to the camera posing problem
Arnaud de Mesmay, Yo'Av Rieck, Martin Tancer and Eric Sedgwick. The Unbearable Hardness of Unknotting
Jacob Fox, Janos Pach and Andrew Suk. Semi-algebraic colorings of complete graphs
Kevin Buchin, Sariel Har-Peled and Dániel Oláh. A Spanner for the Day After
Vincent Cohen-Addad, Éric Colin de Verdière, Dániel Marx and Arnaud de Mesmay. Almost tight lower bounds for hard cutting problems in embedded graphs
Drago Bokal, Zdenek Dvorak, Petr Hlineny, Jesus Leanos, Bojan Mohar and Tilo Wiedera. Bounded maximum degree conjecture holds precisely for c-crossing-critical graphs with c ≤ 12
Karl Bringmann, Marvin Künnemann and André Nusser. Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance
Karl Bringmann and Bhaskar Ray Chaudhury. Polyline Simplification has Cubic Complexity
Anne Driemel, Jeff Phillips and Ioannis Psarros. On the VC dimension of metric balls under Fr'echet and Hausdorff distances
Ching-Hsiang Hsu, Yi-Jen Chiang and Chee Yap. Rods and Rings: Soft Subdivision Planner for R^3 x S^2
David Eppstein. Cubic Planar Graphs That Cannot Be Drawn On Few Lines
David Eppstein. Counting Polygon Triangulations is Hard
Haitao Wang and Jie Xue. Near-optimal Algorithms for Shortest Paths in Weighted Unit-Disk Graphs
Andrey Boris Khesin, Aleksandar Nikolov and Dmitry Paramonov. Preconditioning for the Geometric Transportation Problem
Timothy M. Chan. Dynamic Geometric Data Structures via Shallow Cuttings
Radoslav Fulek and Jan Kynčl. Z_2-genus of graphs and minimum rank of partial symmetric matrices
Jie Xue, Yuan Li, Saladi Rahul and Ravi Janardan. Searching for the closest-pair in a query translate
Benjamin Niedermann, Ignaz Rutter and Matthias Wolf. Efficient Algorithms for Ortho-Radial Graph Drawing
Pankaj K. Agarwal, Hsien-Chih Chang and Allen Xiao. Geometric Partial Matching and Unbalanced Transportation
Kristóf Huszár and Jonathan Spreer. 3-Manifold triangulations with small treewidth
Patrick Schnider. Ham-Sandwich cuts and center transversals in subspaces
Amer Krivosija and Alexander Munteanu. Probabilistic smallest enclosing ball in high dimensions via subgradient sampling
Michael Kerber, Michael Lesnick and Steve Oudot. Exact computation of the matching distance on 2-parameter persistence modules
Radoslav Fulek, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr and Uli Wagner. The Crossing Tverberg Theorem
Siddharth Pritam and Jean-Daniel Boissonnat. Computing Persistent Homology of Flag Complexes via Strong Collapses
Patrizio Angelini, Steven Chaplick, Sabine Cornelsen, Giordano Da Lozzo and Vincenzo Roselli. Morphing Contact Representations of Graphs
Ravid Cohen, Dan Halperin, Pankaj K. Agarwal and Wolfgang Mulzer. Maintaining the Union of Unit Discs under Insertions with Near-Optimal Overhead
Hsien-Chih Chang, Marcos Cossarini and Jeff Erickson. Lower Bounds for Electrical Reduction on Surfaces
Peyman Afshani. A New Lower Bound for Semigroup Orthogonal Range Searching
Jeff Erickson and Yipu Wang. Topologically Trivial Closed Walks in Directed Surface Graphs
Peyman Afshani and Jeff Phillips. Independent Range Sampling, Revisited Again
Ulderico Fugacci and Michael Kerber. Chunk Reduction for Multi-Parameter Persistent Homology
Nathaniel Lahn and Sharath Raghvendra. A Weighted Approach to Maximum Cardinality Bipartite Matching Problem with Applications in Geometric Settings
Ian Munro and Yakov Nekrich. Dynamic Planar Point Location in External Memory
Herbert Edelsbrunner, Žiga Virk and Hubert Wagner. Topological Data Analysis in Information Space
Hugo Akitaya, Matias Korman, Mikhail Rudoy, Diane Souvaine and Csaba Toth. Circumscribing Polygons and Polygonizations for Disjoint Line Segments
Ivor Hoog V.D., Irina Kostitsyna, Bettina Speckmann and Maarten Löffler. Preprocessing Ambiguous Imprecise Points
Mathieu Carrière and Ulrich Bauer. On the Metric Distortion of Embedding Persistence Diagrams into separable Hilbert spaces
Call for Papers The 35th International Symposium on Computational Geometry (SoCG 2019) will be held in Portland, Oregon, June 18-21, 2019, as part of the Computational Geometry (CG) Week. We invite submissions of high quality that describe original research on computational problems in a geometric setting. Topics of interest include, but are not limited to:
  • • Design, analysis, and implementation of geometric algorithms and data structures;
  • • Lower bounds on the computational complexity of geometric problems;
  • • Mathematical, numerical, and algebraic issues arising in the formulation, analysis, implementation, and experimental evaluation of geometric algorithms and heuristics;
  • • Discrete and combinatorial geometry;
  • • Computational topology, topological data analysis, and topological combinatorics;
  • • Applications of computational geometry in any field.

To ensure that a submission is evaluated on its own merits, authors will need to identify the main strengths of their submission, as captured by four possible paper types. Please consult the last section of this CFP (or the conference web-page) for a detailed description of the paper types and associated evaluation criteria. There are no quotas for the paper types and submissions can be labeled with more than one paper type at the time of submission.

EasyChair Link

Important Dates

  • November 28, 2018 (Wednesday): Abstracts due (23:59 PST)
  • December 5, 2018 (Wednesday): Papers due (23:59 PST)
  • February 15, 2019 (Friday): Notification of acceptance/rejection
  • March 15, 2019 (Friday): Final versions of accepted papers due
  • June 18-21, 2019 (Tuesday-Friday): Symposium

Submission Guidelines

Submissions must be formatted in accordance with the LIPIcs proceedings guidelines and not exceed 500 lines, excluding front matter, references, and a clearly marked appendix (further described below). Note that figure and tables are not counted towards the 500 lines, but their captions are. To ensure an accurate line counting, authors must use the LaTeX class file socg-lipics-v2018, which is a wrapper around the standard class. The class file, as well a document describing the motivation and technicalities behind this class, are available from the SoCG webpage Authors should refrain from putting excessive amounts of texts in parts in which lines are not counted automatically. If authors need constructs that contain large amounts of uncounted text, they should compensate for this by reducing the final count accordingly.

Papers should be submitted in the form of an extended abstract, which begins with the title of the paper, each author’s name and affiliation, as well as a short abstract. This should be followed by the main body of the paper that begins with a precise statement of the problem considered, a succinct summary of the results obtained (emphasizing the significance, novelty, and potential impact of the research), and a clear comparison with related work. The remainder of the extended abstract should provide sufficient details to allow the program committee to evaluate the validity, quality, and relevance of the contribution. Clarity of presentation is very important; the entire extended abstract should be written carefully, taking into consideration that it will be read and evaluated by both experts and non-experts, often under tight time constraints. All details needed to verify the results must be provided.

Supporting materials, including proofs of theoretical claims and experimental details, that do not fit in the 500-line limit should be given in an appendix. If more appropriate, the full version may be given as the appendix. In both cases, however, the authors should include in the main part specific pointers to the relevant locations in the appendix. The appendix will be read by the program committee members at their discretion and will not be published as part of the proceedings. Thus, the paper without the appendix should be able to stand on its own. Experimental and implementation results (independent of paper type) must be reproducible and verifiable. Authors of all types of papers are encouraged to put accompanying software and relevant data, if there are any, in a repository accessible to the reviewers. Authors are asked to indicate which of the supporting material will remain publicly available if their papers are accepted.

Submissions deviating from the above guidelines risk being rejected without further consideration.

Results previously published or accepted for publication in the proceedings of another conference cannot be submitted. Simultaneous submissions of the results to another conference with published proceedings are not allowed. Exempted are workshops and conferences without formal proceedings, but possibly with handouts containing short abstracts. Results that have already been accepted (with or without revision) for publication in a journal at the time of their submission to the symposium are not allowed. A paper submitted to a journal but not yet accepted for publication can be submitted to the symposium. In such cases, the authors must mention this on the front page of the submission and clearly identify the status of the journal submission as of November 28, 2018. Format of Accepted Papers

Final proceedings versions of accepted papers must be formatted in accordance with the LIPIcs proceedings guidelines and not exceed 500 lines, excluding a title page and references. These final versions must be submitted by March 15, 2019. If any supporting material (including complete proofs of theoretical claims and experimental details) does not fit in the specified limit, then the full version of the paper containing this information must be referenced in the conference version and made available at a public repository, such as arXiv, by March 15, 2018. Where applicable, we encourage authors to make accompanying software and/or data publicly accessible, with proper references in the paper.

An author of each accepted paper will be expected to attend the symposium and present the paper (approximately 20 minutes). An award will be given to the best paper, and if it is of interest to a broad audience, its authors will be invited to submit an extended version of it to the Journal of the ACM. Authors of a selection of papers from the symposium will be invited to submit extended versions of their papers to special issues of Discrete & Computational Geometry and Journal of Computational Geometry.

Program Committee

  • Hee-Kap Ahn, Pohang Univ. of Science and Technology, South Korea
  • Alexandr Andoni, Columbia University, USA
  • Sunil Arya, Hong Kong Univ. of Science and Technology, China
  • Gill Barequet (co-chair), Technion—Israel Inst. of Technology, Israel
  • Mark de Berg, TU Eindhoven, Netherlands
  • Prosenjit Bose, Carleton University, Canada
  • Frédéric Cazals, INRIA Sophia Antipolis-Méditerrané, France
  • Tamal K. Dey, The Ohio State University, USA
  • Kyle Fox, Univ. of Texas at Dallas, USA
  • Joachim Gudmundsson, Univ. of Sydney, Australia
  • Chaya Keller, Ben Gurion University, Israel
  • Stephen Kobourov, Univ. of Arizona, USA
  • Francis Lazarus, CNRS Grenoble, France
  • Clément Maria, INRIA Sophia Antipolis-Méditerranée, France
  • Tillmann Miltzow, Utrecht University, Netherlands
  • Zuzana Patáková, Inst. of Science and Technology, Austria
  • Amit Patel, Colorado State University, USA
  • Raimund Seidel, Saarland University, Germany
  • Christian Sohler, TU Dortmund, Germany, and Google, Switzerland
  • Noam Solomon, Harvard University, USA
  • Subhash Suri, Univ. of California at Santa Barbara, USA
  • Kasturi Varadarajan, Univ. of Iowa, USA
  • Birgit Vogtenhuber, Graz Univ. of Technology, Austria
  • Bei Wang, University of Utah, USA
  • Yusu Wang (co-chair), The Ohio State University, USA
Proceedings Chair

Matias Korman, Tufts University, USA

Paper types

When writing or evaluating a SoCG paper, it is important to keep in mind that there are different types of contributions, each with their own strengths. Results of all kinds (theoretical and practical) need to be reproducible and verifiable. To ensure that each submission is evaluated on its own merits, authors need to identify the main strengths of their submissions, as captured by four possible paper types. These paper types are described in detail below, together with their associated evaluation criteria. These criteria will serve as the basis for all reviews, both by PC members and by external subreviewers, and for the subsequent discussion in the PC. There are no quotas for the paper types and submissions can be labeled with more than one paper type at the time of submission.

Mathematical Foundations

A typical paper will contain theorems and proofs describing new results in discrete or combinatorial geometry, or in topological combinatorics. The paper will primarily be evaluated on its technical depth, the importance of the results, the elegance of the solution, the connection of the problem studied to computational geometry and topology, and the potential future impact on algorithm development.

Algorithmic Complexity

A typical paper will contain algorithms, data structures, theorems, proofs, or lower bound constructions describing new results on computational geometry problems. The paper will primarily be evaluated on the (mathematical or computational) relevance and importance of the problem studied, its technical depth, the elegance of the solution, and the potential future impact of the results or the proposed new methods and techniques.

Experimental & Implementation

A typical paper will make a clear contribution to the implementation and evaluation of geometric algorithms, such as exact, approximate, or algebraic computation, algorithms engineering, or the experimental evaluation of competing algorithmic approaches. The paper will primarily be evaluated on the completeness and the expected impact of the proposed implementation, the soundness of the experiments, the quality and quantity of testing, and on the general amount of knowledge gained.


A typical paper will describe the modeling and algorithmic choices made when developing or adapting computational geometry techniques for an application area. The paper will be primarily evaluated on the soundness of the modeling decisions, the ingenuity of the solution, the effectiveness of the proposed method, and the expected impact in the application area. One might also consider the lesson learned regarding the applicability or suitability of computational geometry tools to the specific area.