SoCG 2018 June 11-14, 2018 - Budapest, Hungary

34th International Symposium on Computational Geometry (SoCG 2018)



Bettina Speckmann and Csaba D. Tóth (Eds.)
ISBN 978-3-95977-066-8, LIPICS Vol. 99 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 53 MB)
Search Publication Server


Authors
  • Abdelkader, Ahmed
  • Abu-Affash, A. Karim
  • Adamaszek, Michal
  • Adams, Henry
  • Agarwal, Pankaj K.
  • Ahn, Hee-Kap
  • Arge, Lars
  • Ashida, Ryo
  • Bae, Sang Won
  • Bajaj, Chandrajit L.
  • Bandyapadhyay, Sayan
  • Becker, Aaron T.
  • Bhowmick, Santanu
  • Biniaz, Ahmad
  • Bjerkevik, Hĺvard Bakke
  • Boissonnat, Jean-Daniel
  • Bonnet, Édouard
  • Bose, Prosenjit
  • Botnan, Magnus Bakke
  • Brown, Adam
  • Buchet, Mickaël
  • Buchin, Kevin
  • Bukh, Boris
  • Burton, Benjamin A.
  • Butt, Nabeel
  • C. S., Karthik
  • Cabello, Sergio
  • Calčs, Ludovic
  • Cardinal, Jean
  • Carmi, Paz
  • Carpenter, Timothy
  • Chalkis, Apostolos
  • Chalopin, Jérémie
  • Chan, Timothy M.
  • Chazal, Frédéric
  • Cheong, Otfried
  • Chepoi, Victor
  • Choi, Yoonsung
  • David, Roee
  • Demaine, Erik D.
  • Demas, Dani
  • Devadoss, Satyan L.
  • Devillers, Olivier
  • Dey, Tamal K.
  • Divol, Vincent
  • Dragan, Feodor F.
  • Ducoffe, Guillaume
  • Dvorák, Zdenek
  • Dyer, Ramsay
  • Ebeida, Mohamed S.
  • Edelsbrunner, Herbert
  • Elkin, Michael
  • Emiris, Ioannis Z.
  • Escolar, Emerson G.
  • Fekete, Sándor P.
  • Felsner, Stefan
  • Fisikopoulos, Vissarion
  • Fomin, Fedor V.
  • Fulek, Radoslav
  • Gasparovic, Ellen
  • Ghosh, Arijit
  • Giannopoulos, Panos
  • Goaoc, Xavier
  • Gommel, Maria
  • Grochow, Joshua A.
  • Haas, Andreas
  • Hlinený, Petr
  • Hong, Yu Xuan
  • Hoog v.d., Ivor
  • Hubard, Alfredo
  • Huszár, Kristóf
  • Iacono, John
  • Inamdar, Tanmay
  • Janardan, Ravi
  • Jartoux, Bruno
  • Jin, Yifei
  • Johnson, Daniel D.
  • Junginger, Kolja
  • Keldenich, Phillip
  • Keller, Chaya
  • Keszegh, Balázs
  • Khramtcova, Elena
  • Kim, Eun Jung
  • Kleist, Linda
  • Klute, Fabian
  • Knudson, Kevin
  • Konitzny, Matthias
  • Kostitsyna, Irina
  • Kouhestani, Bahram
  • Kyncl, Jan
  • Löffler, Maarten
  • Laarhoven, Thijs
  • Laekhanukit, Bundit
  • Langerman, Stefan
  • Lazard, Sylvain
  • Lee, Justin
  • Lenhart, William J.
  • Li, Jian
  • Li, Yuan
  • Lieutier, André
  • Lin, Lillian
  • Liu, Chih-Hung
  • Lokshtanov, Daniel
  • Mütze, Torsten
  • Magnard, Thomas
  • Maheshwari, Anil
  • Mahmoud, Ahmed H.
  • Martínez-Sandoval, Leonardo
  • Meijer, Henk
  • Milatz, Malte
  • Milenkovic, Victor
  • Mitchell, Scott A.
  • Mohammed, Abdulhakeem
  • Mohar, Bojan
  • Morin, Pat
  • Munro, Ian
  • Mustafa, Nabil H.
  • Nöllenburg, Martin
  • Nakagawa, Kotaro
  • Neiman, Ofer
  • O'Rourke, Joseph
  • Oh, Eunjin
  • Ooms, Aurélien
  • Osang, Georg
  • Owens, John D.
  • Pach, János
  • Papadopoulou, Evanthia
  • Paták, Pavel
  • Patáková, Zuzana
  • Phillips, Jeff M.
  • Psarros, Ioannis
  • Purvine, Emilie
  • Raghvendra, Sharath
  • Rahul, Saladi
  • Rappaport, David
  • Reed, Bruce
  • Roche-Newton, Oliver
  • Roldán-Pensado, Edgardo
  • Rubin, Natan
  • Rushdi, Ahmad A.
  • Rzazewski, Pawel
  • Sacks, Elisha
  • Saurabh, Saket
  • Sazdanovic, Radmila
  • Scheffer, Christian
  • Sering, Leon
  • Sidiropoulos, Anastasios
  • Sikora, Florian
  • Singhal, Kritika
  • Skrepetos, Dimitrios
  • Smid, Michiel
  • Smorodinsky, Shakhar
  • Speckmann, Bettina
  • Spreer, Jonathan
  • Sridhar, Vijay
  • Staals, Frank
  • Stehn, Fabian
  • Tóth, Csaba D.
  • Tóth, Géza
  • Tai, Wai Ming
  • Tancer, Martin
  • Tang, Pingfan
  • Tillmann, Stephan
  • Trager, Matthew
  • Tsakalidis, Konstantinos
  • Tucker-Foltz, Jamie
  • van Goethem, Arthur
  • van Kreveld, Marc
  • Varadarajan, Kasturi
  • Vaxčs, Yann
  • Verbeek, Kevin
  • Verdičre, Éric Colin de
  • Virk, Ziga
  • Wagner, Hubert
  • Wagner, Uli
  • Wang, Bei
  • Wang, Haitao
  • Wang, Jiayuan
  • Wang, Yusu
  • Warley, Jackson
  • Wintraecken, Mathijs
  • Wiratma, Lionov
  • Xin, Cheng
  • Xue, Jie
  • Yoon, Sang Duk
  • Yuditsky, Yelena
  • Zhan, Wei
  • Zhang, Jingru
  • Ziegelmeier, Lori

  •   
    Front Matter, Table of Contents, Foreword, Conference Organization, Additional Reviewers, Acknowledgement of Support, Invited Talks
    Authors: Speckmann, Bettina ; Tóth, Csaba D.

    Abstract | Document (397 KB) | BibTeX

    Sampling Conditions for Conforming Voronoi Meshing by the VoroCrust Algorithm
    Authors: Abdelkader, Ahmed ; Bajaj, Chandrajit L. ; Ebeida, Mohamed S. ; Mahmoud, Ahmed H. ; Mitchell, Scott A. ; Owens, John D. ; Rushdi, Ahmad A.

    Abstract | Document (3,468 KB) | BibTeX

    Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs
    Authors: Abu-Affash, A. Karim ; Carmi, Paz ; Maheshwari, Anil ; Morin, Pat ; Smid, Michiel ; Smorodinsky, Shakhar

    Abstract | Document (649 KB) | BibTeX

    Vietoris-Rips and Cech Complexes of Metric Gluings
    Authors: Adamaszek, Michal ; Adams, Henry ; Gasparovic, Ellen ; Gommel, Maria ; Purvine, Emilie ; Sazdanovic, Radmila ; Wang, Bei ; Wang, Yusu ; Ziegelmeier, Lori

    Abstract | Document (609 KB) | BibTeX

    Improved Dynamic Geodesic Nearest Neighbor Searching in a Simple Polygon
    Authors: Agarwal, Pankaj K. ; Arge, Lars ; Staals, Frank

    Abstract | Document (585 KB) | BibTeX

    O~(n^{1/3})-Space Algorithm for the Grid Graph Reachability Problem
    Authors: Ashida, Ryo ; Nakagawa, Kotaro

    Abstract | Document (653 KB) | BibTeX

    The Reverse Kakeya Problem
    Authors: Bae, Sang Won ; Cabello, Sergio ; Cheong, Otfried ; Choi, Yoonsung ; Stehn, Fabian ; Yoon, Sang Duk

    Abstract | Document (599 KB) | BibTeX

    Capacitated Covering Problems in Geometric Spaces
    Authors: Bandyapadhyay, Sayan ; Bhowmick, Santanu ; Inamdar, Tanmay ; Varadarajan, Kasturi

    Abstract | Document (383 KB) | BibTeX

    Faster Algorithms for some Optimization Problems on Collinear Points
    Authors: Biniaz, Ahmad ; Bose, Prosenjit ; Carmi, Paz ; Maheshwari, Anil ; Munro, Ian ; Smid, Michiel

    Abstract | Document (801 KB) | BibTeX

    Local Criteria for Triangulation of Manifolds
    Authors: Boissonnat, Jean-Daniel ; Dyer, Ramsay ; Ghosh, Arijit ; Wintraecken, Mathijs

    Abstract | Document (493 KB) | BibTeX

    The Reach, Metric Distortion, Geodesic Convexity and the Variation of Tangent Spaces
    Authors: Boissonnat, Jean-Daniel ; Lieutier, André ; Wintraecken, Mathijs

    Abstract | Document (722 KB) | BibTeX

    Orthogonal Terrain Guarding is NP-complete
    Authors: Bonnet, Édouard ; Giannopoulos, Panos

    Abstract | Document (486 KB) | BibTeX

    QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs
    Authors: Bonnet, Édouard ; Giannopoulos, Panos ; Kim, Eun Jung ; Rzazewski, Pawel ; Sikora, Florian

    Abstract | Document (497 KB) | BibTeX

    Computational Complexity of the Interleaving Distance
    Authors: Bjerkevik, Hĺvard Bakke ; Botnan, Magnus Bakke

    Abstract | Document (545 KB) | BibTeX

    Sheaf-Theoretic Stratification Learning
    Authors: Brown, Adam ; Wang, Bei

    Abstract | Document (510 KB) | BibTeX

    Realizations of Indecomposable Persistence Modules of Arbitrarily Large Dimension
    Authors: Buchet, Mickaël ; Escolar, Emerson G.

    Abstract | Document (491 KB) | BibTeX

    Approximating the Distribution of the Median and other Robust Estimators on Uncertain Data
    Authors: Buchin, Kevin ; Phillips, Jeff M. ; Tang, Pingfan

    Abstract | Document (592 KB) | BibTeX

    Consistent Sets of Lines with no Colorful Incidence
    Authors: Bukh, Boris ; Goaoc, Xavier ; Hubard, Alfredo ; Trager, Matthew

    Abstract | Document (1,041 KB) | BibTeX

    The HOMFLY-PT Polynomial is Fixed-Parameter Tractable
    Authors: Burton, Benjamin A.

    Abstract | Document (1,029 KB) | BibTeX

    Practical Volume Computation of Structured Convex Bodies, and an Application to Modeling Portfolio Dependencies and Financial Crises
    Authors: Calčs, Ludovic ; Chalkis, Apostolos ; Emiris, Ioannis Z. ; Fisikopoulos, Vissarion

    Abstract | Document (751 KB) | BibTeX

    Subquadratic Encodings for Point Configurations
    Authors: Cardinal, Jean ; Chan, Timothy M. ; Iacono, John ; Langerman, Stefan ; Ooms, Aurélien

    Abstract | Document (601 KB) | BibTeX

    Algorithms for Low-Distortion Embeddings into Arbitrary 1-Dimensional Spaces
    Authors: Carpenter, Timothy ; Fomin, Fedor V. ; Lokshtanov, Daniel ; Saurabh, Saket ; Sidiropoulos, Anastasios

    Abstract | Document (450 KB) | BibTeX

    Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs
    Authors: Chalopin, Jérémie ; Chepoi, Victor ; Dragan, Feodor F. ; Ducoffe, Guillaume ; Mohammed, Abdulhakeem ; Vaxčs, Yann

    Abstract | Document (493 KB) | BibTeX

    Tree Drawings Revisited
    Authors: Chan, Timothy M.

    Abstract | Document (580 KB) | BibTeX

    Approximate Shortest Paths and Distance Oracles in Weighted Unit-Disk Graphs
    Authors: Chan, Timothy M. ; Skrepetos, Dimitrios

    Abstract | Document (483 KB) | BibTeX

    Dynamic Planar Orthogonal Point Location in Sublogarithmic Time
    Authors: Chan, Timothy M. ; Tsakalidis, Konstantinos

    Abstract | Document (434 KB) | BibTeX

    The Density of Expected Persistence Diagrams and its Kernel Based Estimation
    Authors: Chazal, Frédéric ; Divol, Vincent

    Abstract | Document (803 KB) | BibTeX

    Embedding Graphs into Two-Dimensional Simplicial Complexes
    Authors: Verdičre, Éric Colin de ; Magnard, Thomas ; Mohar, Bojan

    Abstract | Document (465 KB) | BibTeX

    On the Complexity of Closest Pair via Polar-Pair of Point-Sets
    Authors: David, Roee ; C. S., Karthik ; Laekhanukit, Bundit

    Abstract | Document (580 KB) | BibTeX

    Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch
    Authors: Demaine, Erik D. ; Fekete, Sándor P. ; Keldenich, Phillip ; Scheffer, Christian ; Meijer, Henk

    Abstract | Document (577 KB) | BibTeX

    3D Snap Rounding
    Authors: Devillers, Olivier ; Lazard, Sylvain ; Lenhart, William J.

    Abstract | Document (782 KB) | BibTeX

    Graph Reconstruction by Discrete Morse Theory
    Authors: Dey, Tamal K. ; Wang, Jiayuan ; Wang, Yusu

    Abstract | Document (1,515 KB) | BibTeX

    Computing Bottleneck Distance for 2-D Interval Decomposable Modules
    Authors: Dey, Tamal K. ; Xin, Cheng

    Abstract | Document (827 KB) | BibTeX

    Structure and Generation of Crossing-Critical Graphs
    Authors: Dvorák, Zdenek ; Hlinený, Petr ; Mohar, Bojan

    Abstract | Document (568 KB) | BibTeX

    The Multi-cover Persistence of Euclidean Balls
    Authors: Edelsbrunner, Herbert ; Osang, Georg

    Abstract | Document (516 KB) | BibTeX

    Smallest Enclosing Spheres and Chernoff Points in BregmanGeometry
    Authors: Edelsbrunner, Herbert ; Virk, Ziga ; Wagner, Hubert

    Abstract | Document (478 KB) | BibTeX

    Near Isometric Terminal Embeddings for Doubling Metrics
    Authors: Elkin, Michael ; Neiman, Ofer

    Abstract | Document (492 KB) | BibTeX

    Products of Euclidean Metrics and Applications to Proximity Questions among Curves
    Authors: Emiris, Ioannis Z. ; Psarros, Ioannis

    Abstract | Document (490 KB) | BibTeX

    Rainbow Cycles in Flip Graphs
    Authors: Felsner, Stefan ; Kleist, Linda ; Mütze, Torsten ; Sering, Leon

    Abstract | Document (998 KB) | BibTeX

    Hanani-Tutte for Approximating Maps of Graphs
    Authors: Fulek, Radoslav ; Kyncl, Jan

    Abstract | Document (702 KB) | BibTeX

    The Z_2-Genus of Kuratowski Minors
    Authors: Fulek, Radoslav ; Kyncl, Jan

    Abstract | Document (504 KB) | BibTeX

    Shellability is NP-Complete
    Authors: Goaoc, Xavier ; Paták, Pavel ; Patáková, Zuzana ; Tancer, Martin ; Wagner, Uli

    Abstract | Document (702 KB) | BibTeX

    Optimal Morphs of Planar Orthogonal Drawings
    Authors: van Goethem, Arthur ; Verbeek, Kevin

    Abstract | Document (807 KB) | BibTeX

    Computational Topology and the Unique Games Conjecture
    Authors: Grochow, Joshua A. ; Tucker-Foltz, Jamie

    Abstract | Document (500 KB) | BibTeX

    Solving Large-Scale Minimum-Weight Triangulation Instances to Provable Optimality
    Authors: Haas, Andreas

    Abstract | Document (538 KB) | BibTeX

    Dynamic Smooth Compressed Quadtrees
    Authors: Hoog v.d., Ivor ; Khramtcova, Elena ; Löffler, Maarten

    Abstract | Document (635 KB) | BibTeX

    On the Treewidth of Triangulated 3-Manifolds
    Authors: Huszár, Kristóf ; Spreer, Jonathan ; Wagner, Uli

    Abstract | Document (627 KB) | BibTeX

    On Partial Covering For Geometric Set Systems
    Authors: Inamdar, Tanmay ; Varadarajan, Kasturi

    Abstract | Document (536 KB) | BibTeX

    Optimality of Geometric Local Search
    Authors: Jartoux, Bruno ; Mustafa, Nabil H.

    Abstract | Document (545 KB) | BibTeX

    Odd Yao-Yao Graphs are Not Spanners
    Authors: Jin, Yifei ; Li, Jian ; Zhan, Wei

    Abstract | Document (1,868 KB) | BibTeX

    Deletion in Abstract Voronoi Diagrams in Expected Linear Time
    Authors: Junginger, Kolja ; Papadopoulou, Evanthia

    Abstract | Document (1,477 KB) | BibTeX

    From a (p,2)-Theorem to a Tight (p,q)-Theorem
    Authors: Keller, Chaya ; Smorodinsky, Shakhar

    Abstract | Document (472 KB) | BibTeX

    Coloring Intersection Hypergraphs of Pseudo-Disks
    Authors: Keszegh, Balázs

    Abstract | Document (577 KB) | BibTeX

    Minimizing Crossings in Constrained Two-Sided Circular Graph Layouts
    Authors: Klute, Fabian ; Nöllenburg, Martin

    Abstract | Document (594 KB) | BibTeX

    Discrete Stratified Morse Theory: A User's Guide
    Authors: Knudson, Kevin ; Wang, Bei

    Abstract | Document (684 KB) | BibTeX

    An Optimal Algorithm to Compute the Inverse Beacon Attraction Region
    Authors: Kostitsyna, Irina ; Kouhestani, Bahram ; Langerman, Stefan ; Rappaport, David

    Abstract | Document (756 KB) | BibTeX

    On Optimal Polyline Simplification Using the Hausdorff and Fréchet Distance
    Authors: van Kreveld, Marc ; Löffler, Maarten ; Wiratma, Lionov

    Abstract | Document (806 KB) | BibTeX

    Graph-Based Time-Space Trade-Offs for Approximate Near Neighbors
    Authors: Laarhoven, Thijs

    Abstract | Document (610 KB) | BibTeX

    A Nearly Optimal Algorithm for the Geodesic Voronoi Diagram of Points in a Simple Polygon
    Authors: Liu, Chih-Hung

    Abstract | Document (520 KB) | BibTeX

    Further Consequences of the Colorful Helly Hypothesis
    Authors: Martínez-Sandoval, Leonardo ; Roldán-Pensado, Edgardo ; Rubin, Natan

    Abstract | Document (533 KB) | BibTeX

    Random Walks on Polytopes of Constant Corank
    Authors: Milatz, Malte

    Abstract | Document (619 KB) | BibTeX

    Table Based Detection of Degenerate Predicates in Free Space Construction
    Authors: Milenkovic, Victor ; Sacks, Elisha ; Butt, Nabeel

    Abstract | Document (4,287 KB) | BibTeX

    Approximate Range Queries for Clustering
    Authors: Oh, Eunjin ; Ahn, Hee-Kap

    Abstract | Document (461 KB) | BibTeX

    Point Location in Dynamic Planar Subdivisions
    Authors: Oh, Eunjin ; Ahn, Hee-Kap

    Abstract | Document (475 KB) | BibTeX

    Edge-Unfolding Nearly Flat Convex Caps
    Authors: O'Rourke, Joseph

    Abstract | Document (3,333 KB) | BibTeX

    A Crossing Lemma for Multigraphs
    Authors: Pach, János ; Tóth, Géza

    Abstract | Document (521 KB) | BibTeX

    Near-Optimal Coresets of Kernel Density Estimates
    Authors: Phillips, Jeff M. ; Tai, Wai Ming

    Abstract | Document (592 KB) | BibTeX

    Optimal Analysis of an Online Algorithm for the Bipartite Matching Problem on a Line
    Authors: Raghvendra, Sharath

    Abstract | Document (482 KB) | BibTeX

    Almost All String Graphs are Intersection Graphs of Plane Convex Sets
    Authors: Pach, János ; Reed, Bruce ; Yuditsky, Yelena

    Abstract | Document (608 KB) | BibTeX

    An Improved Bound for the Size of the Set A/A+A
    Authors: Roche-Newton, Oliver

    Abstract | Document (425 KB) | BibTeX

    Fractal Dimension and Lower Bounds for Geometric Problems
    Authors: Sidiropoulos, Anastasios ; Singhal, Kritika ; Sridhar, Vijay

    Abstract | Document (614 KB) | BibTeX

    The Trisection Genus of Standard Simply Connected PL 4-Manifolds
    Authors: Spreer, Jonathan ; Tillmann, Stephan

    Abstract | Document (1,230 KB) | BibTeX

    An O(n log n)-Time Algorithm for the k-Center Problem in Trees
    Authors: Wang, Haitao ; Zhang, Jingru

    Abstract | Document (488 KB) | BibTeX

    New Bounds for Range Closest-Pair Problems
    Authors: Xue, Jie ; Li, Yuan ; Rahul, Saladi ; Janardan, Ravi

    Abstract | Document (687 KB) | BibTeX

    Coordinated Motion Planning: The Video (Multimedia Exposition)
    Authors: Becker, Aaron T. ; Fekete, Sándor P. ; Keldenich, Phillip ; Konitzny, Matthias ; Lin, Lillian ; Scheffer, Christian

    Abstract | Document (6,710 KB) | BibTeX

    Geometric Realizations of the 3D Associahedron (Multimedia Exposition)
    Authors: Devadoss, Satyan L. ; Johnson, Daniel D. ; Lee, Justin ; Warley, Jackson

    Abstract | Document (847 KB) | BibTeX

    Star Unfolding of Boxes (Multimedia Exposition)
    Authors: Demas, Dani ; Devadoss, Satyan L. ; Hong, Yu Xuan

    Abstract | Document (858 KB) | BibTeX

    VoroCrust Illustrated: Theory and Challenges (Multimedia Exposition)
    Authors: Abdelkader, Ahmed ; Bajaj, Chandrajit L. ; Ebeida, Mohamed S. ; Mahmoud, Ahmed H. ; Mitchell, Scott A. ; Owens, John D. ; Rushdi, Ahmad A.

    Abstract | Document (432 KB) | BibTeX

      




    DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI