SoCG 2019 June 18-21, 2019, Portland, Oregon, USA

35th International Symposium on Computational Geometry (SoCG 2019)



Gill Barequet and Yusu Wang (Eds.)
ISBN 978-3-95977-104-7, LIPICS Vol. 129 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 44 MB)
Search Publication Server


Authors
  • Afshani, Peyman
  • Agarwal, Pankaj K.
  • Agrawal, Akanksha
  • Aiger, Dror
  • Akitaya, Hugo A.
  • Anai, Hirokazu
  • Angelini, Patrizio
  • Aronov, Boris
  • Attali, Dominique
  • Barba, Luis
  • Barequet, Gill
  • Bauer, Ulrich
  • Becker, Aaron T.
  • Ben-Shachar, Gil
  • Binucci, Carla
  • Boissonnat, Jean-Daniel
  • Bokal, Drago
  • Braverman, Vladimir
  • Bringmann, Karl
  • Buchin, Kevin
  • Cabello, Sergio
  • Carričre, Mathieu
  • Chan, Timothy M.
  • Chang, Hsien-Chih
  • Chaplick, Steven
  • Charikar, Moses
  • Chaudhury, Bhaskar Ray
  • Chazal, Frédéric
  • Chiang, Yi-Jen
  • Cohen, Ravid
  • Cohen-Addad, Vincent
  • Colin de Verdičre, Éric
  • Cornelsen, Sabine
  • Cossarini, Marcos
  • Da Lozzo, Giordano
  • Dasgupta, Sanjoy
  • De Carufel, Jean-Lou
  • de Mesmay, Arnaud
  • Didimo, Walter
  • Di Giacomo, Emilio
  • Donald, Bruce R.
  • Driemel, Anne
  • Dujmovic, Vida
  • Dumitrescu, Adrian
  • Dvorák, Zdenek
  • Edelsbrunner, Herbert
  • Eppstein, David
  • Erickson, Jeff
  • Ezra, Esther
  • Fekete, Sándor P.
  • Fox, Jacob
  • Fugacci, Ulderico
  • Fulek, Radoslav
  • Gärtner, Bernd
  • Glisse, Marc
  • Goaoc, Xavier
  • Guspiel, Grzegorz
  • Halperin, Dan
  • Har-Peled, Sariel
  • Hlinený, Petr
  • Holmsen, Andreas
  • Hsu, Ching-Hsiang
  • Huszár, Kristóf
  • Ihara, Diego
  • Ike, Yuichi
  • Inakoshi, Hiroya
  • Janardan, Ravi
  • Jones, Mitchell
  • Künnemann, Marvin
  • Kaplan, Haim
  • Keldenich, Phillip
  • Kerber, Michael
  • Khesin, Andrey Boris
  • Kokiopoulou, Efi
  • Korman, Matias
  • Kostitsyna, Irina
  • Krivosija, Amer
  • Kupavskii, Andrey
  • Kuszmaul, William
  • Kyncl, Jan
  • Löffler, Maarten
  • Lahn, Nathaniel
  • Leańos, Jesús
  • Lesnick, Michael
  • Li, Yuan
  • Lieutier, André
  • Madathil, Jayakrishnan
  • Marx, Dániel
  • Mchedlidze, Tamara
  • Meulemans, Wouter
  • Mirzaei, Mozhgan
  • Mohammadi, Neshat
  • Mohar, Bojan
  • Moran, Shay
  • Morin, Pat
  • Morr, Sebastian
  • Mulzer, Wolfgang
  • Munro, J. Ian
  • Munteanu, Alexander
  • Nekrich, Yakov
  • Nicaud, Cyril
  • Niedermann, Benjamin
  • Nikolov, Aleksandar
  • Nusser, André
  • Oláh, Dániel
  • Ophelders, Tim
  • Oudot, Steve
  • Pach, János
  • Paramonov, Dmitry
  • Patrignani, Maurizio
  • Pennarun, Claire
  • Phillips, Jeff M.
  • Pritam, Siddharth
  • Psarros, Ioannis
  • Raghvendra, Sharath
  • Rahul, Saladi
  • Rieck, Yo'av
  • Roselli, Vincenzo
  • Rudoy, Mikhail
  • Rutter, Ignaz
  • Salinas, David
  • Saurabh, Saket
  • Schäfer, Peter
  • Scheffer, Christian
  • Schnider, Patrick
  • Sedgwick, Eric
  • Sharir, Micha
  • Sidiropoulos, Anastasios
  • Souvaine, Diane L.
  • Speckmann, Bettina
  • Spreer, Jonathan
  • Suk, Andrew
  • Tóth, Csaba D.
  • Tancer, Martin
  • Tao, Yufei
  • Tinarrage, Raphaël
  • Tomon, István
  • Umeda, Yuhei
  • Valtr, Pavel
  • van der Hoog, Ivor
  • Verdonschot, Sander
  • Virk, Ziga
  • Wagner, Hubert
  • Wagner, Uli
  • Wang, Haitao
  • Wang, Yipu
  • Wang, Yu
  • Wang, Yusu
  • Wiedera, Tilo
  • Wolf, Matthias
  • Woodruff, David P.
  • Xiao, Allen
  • Xue, Jie
  • Yang, Lin F.
  • Yap, Chee
  • Yehudayoff, Amir
  • Zahl, Joshua
  • Zehavi, Meirav
  • Zeisl, Bernhard
  • Ziv, Chen

  •   
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Barequet, Gill ; Wang, Yusu

    Abstract | Document (333 KB) | BibTeX

    A Geometric Data Structure from Neuroscience (Invited Talk)
    Authors: Dasgupta, Sanjoy

    Abstract | Document (178 KB) | BibTeX

    Some Geometric and Computational Challenges Arising in Structural Molecular Biology (Invited Talk)
    Authors: Donald, Bruce R.

    Abstract | Document (285 KB) | BibTeX

    A New Lower Bound for Semigroup Orthogonal Range Searching
    Authors: Afshani, Peyman

    Abstract | Document (693 KB) | BibTeX

    Independent Range Sampling, Revisited Again
    Authors: Afshani, Peyman ; Phillips, Jeff M.

    Abstract | Document (467 KB) | BibTeX

    An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
    Authors: Agarwal, Pankaj K. ; Aronov, Boris ; Ezra, Esther ; Zahl, Joshua

    Abstract | Document (520 KB) | BibTeX

    Efficient Algorithms for Geometric Partial Matching
    Authors: Agarwal, Pankaj K. ; Chang, Hsien-Chih ; Xiao, Allen

    Abstract | Document (477 KB) | BibTeX

    Connecting the Dots (with Minimum Crossings)
    Authors: Agrawal, Akanksha ; Guspiel, Grzegorz ; Madathil, Jayakrishnan ; Saurabh, Saket ; Zehavi, Meirav

    Abstract | Document (2,199 KB) | BibTeX

    General Techniques for Approximate Incidences and Their Application to the Camera Posing Problem
    Authors: Aiger, Dror ; Kaplan, Haim ; Kokiopoulou, Efi ; Sharir, Micha ; Zeisl, Bernhard

    Abstract | Document (574 KB) | BibTeX

    Circumscribing Polygons and Polygonizations for Disjoint Line Segments
    Authors: Akitaya, Hugo A. ; Korman, Matias ; Rudoy, Mikhail ; Souvaine, Diane L. ; Tóth, Csaba D.

    Abstract | Document (952 KB) | BibTeX

    Morphing Contact Representations of Graphs
    Authors: Angelini, Patrizio ; Chaplick, Steven ; Cornelsen, Sabine ; Da Lozzo, Giordano ; Roselli, Vincenzo

    Abstract | Document (1,746 KB) | BibTeX

    When Convexity Helps Collapsing Complexes
    Authors: Attali, Dominique ; Lieutier, André ; Salinas, David

    Abstract | Document (531 KB) | BibTeX

    Optimal Algorithm for Geodesic Farthest-Point Voronoi Diagrams
    Authors: Barba, Luis

    Abstract | Document (663 KB) | BibTeX

    Upward Book Embeddings of st-Graphs
    Authors: Binucci, Carla ; Da Lozzo, Giordano ; Di Giacomo, Emilio ; Didimo, Walter ; Mchedlidze, Tamara ; Patrignani, Maurizio

    Abstract | Document (1,313 KB) | BibTeX

    Bounded Degree Conjecture Holds Precisely for c-Crossing-Critical Graphs with c <= 12
    Authors: Bokal, Drago ; Dvorák, Zdenek ; Hlinený, Petr ; Leańos, Jesús ; Mohar, Bojan ; Wiedera, Tilo

    Abstract | Document (566 KB) | BibTeX

    Preconditioning for the Geometric Transportation Problem
    Authors: Khesin, Andrey Boris ; Nikolov, Aleksandar ; Paramonov, Dmitry

    Abstract | Document (545 KB) | BibTeX

    The One-Way Communication Complexity of Dynamic Time Warping Distance
    Authors: Braverman, Vladimir ; Charikar, Moses ; Kuszmaul, William ; Woodruff, David P. ; Yang, Lin F.

    Abstract | Document (473 KB) | BibTeX

    Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance
    Authors: Bringmann, Karl ; Künnemann, Marvin ; Nusser, André

    Abstract | Document (1,306 KB) | BibTeX

    Polyline Simplification has Cubic Complexity
    Authors: Bringmann, Karl ; Chaudhury, Bhaskar Ray

    Abstract | Document (826 KB) | BibTeX

    A Spanner for the Day After
    Authors: Buchin, Kevin ; Har-Peled, Sariel ; Oláh, Dániel

    Abstract | Document (811 KB) | BibTeX

    Computing Shapley Values in the Plane
    Authors: Cabello, Sergio ; Chan, Timothy M.

    Abstract | Document (1,107 KB) | BibTeX

    On the Metric Distortion of Embedding Persistence Diagrams into Separable Hilbert Spaces
    Authors: Carričre, Mathieu ; Bauer, Ulrich

    Abstract | Document (647 KB) | BibTeX

    Convex Polygons in Cartesian Products
    Authors: De Carufel, Jean-Lou ; Dumitrescu, Adrian ; Meulemans, Wouter ; Ophelders, Tim ; Pennarun, Claire ; Tóth, Csaba D. ; Verdonschot, Sander

    Abstract | Document (628 KB) | BibTeX

    Smallest k-Enclosing Rectangle Revisited
    Authors: Chan, Timothy M. ; Har-Peled, Sariel

    Abstract | Document (694 KB) | BibTeX

    Dynamic Geometric Data Structures via Shallow Cuttings
    Authors: Chan, Timothy M.

    Abstract | Document (476 KB) | BibTeX

    Lower Bounds for Electrical Reduction on Surfaces
    Authors: Chang, Hsien-Chih ; Cossarini, Marcos ; Erickson, Jeff

    Abstract | Document (1,090 KB) | BibTeX

    Maintaining the Union of Unit Discs Under Insertions with Near-Optimal Overhead
    Authors: Agarwal, Pankaj K. ; Cohen, Ravid ; Halperin, Dan ; Mulzer, Wolfgang

    Abstract | Document (818 KB) | BibTeX

    Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs
    Authors: Cohen-Addad, Vincent ; Colin de Verdičre, Éric ; Marx, Dániel ; de Mesmay, Arnaud

    Abstract | Document (577 KB) | BibTeX

    The VC Dimension of Metric Balls Under Fréchet and Hausdorff Distances
    Authors: Driemel, Anne ; Phillips, Jeff M. ; Psarros, Ioannis

    Abstract | Document (709 KB) | BibTeX

    Dual Circumference and Collinear Sets
    Authors: Dujmovic, Vida ; Morin, Pat

    Abstract | Document (1,068 KB) | BibTeX

    A Product Inequality for Extreme Distances
    Authors: Dumitrescu, Adrian

    Abstract | Document (494 KB) | BibTeX

    Topological Data Analysis in Information Space
    Authors: Edelsbrunner, Herbert ; Virk, Ziga ; Wagner, Hubert

    Abstract | Document (1,323 KB) | BibTeX

    Cubic Planar Graphs That Cannot Be Drawn On Few Lines
    Authors: Eppstein, David

    Abstract | Document (842 KB) | BibTeX

    Counting Polygon Triangulations is Hard
    Authors: Eppstein, David

    Abstract | Document (906 KB) | BibTeX

    Topologically Trivial Closed Walks in Directed Surface Graphs
    Authors: Erickson, Jeff ; Wang, Yipu

    Abstract | Document (1,855 KB) | BibTeX

    Packing Disks into Disks with Optimal Worst-Case Density
    Authors: Fekete, Sándor P. ; Keldenich, Phillip ; Scheffer, Christian

    Abstract | Document (1,014 KB) | BibTeX

    Semi-Algebraic Colorings of Complete Graphs
    Authors: Fox, Jacob ; Pach, János ; Suk, Andrew

    Abstract | Document (441 KB) | BibTeX

    Chunk Reduction for Multi-Parameter Persistent Homology
    Authors: Fugacci, Ulderico ; Kerber, Michael

    Abstract | Document (707 KB) | BibTeX

    The Crossing Tverberg Theorem
    Authors: Fulek, Radoslav ; Gärtner, Bernd ; Kupavskii, Andrey ; Valtr, Pavel ; Wagner, Uli

    Abstract | Document (547 KB) | BibTeX

    Z_2-Genus of Graphs and Minimum Rank of Partial Symmetric Matrices
    Authors: Fulek, Radoslav ; Kyncl, Jan

    Abstract | Document (614 KB) | BibTeX

    An Experimental Study of Forbidden Patterns in Geometric Permutations by Combinatorial Lifting
    Authors: Goaoc, Xavier ; Holmsen, Andreas ; Nicaud, Cyril

    Abstract | Document (749 KB) | BibTeX

    Journey to the Center of the Point Set
    Authors: Har-Peled, Sariel ; Jones, Mitchell

    Abstract | Document (565 KB) | BibTeX

    Preprocessing Ambiguous Imprecise Points
    Authors: van der Hoog, Ivor ; Kostitsyna, Irina ; Löffler, Maarten ; Speckmann, Bettina

    Abstract | Document (830 KB) | BibTeX

    Rods and Rings: Soft Subdivision Planner for R^3 x S^2
    Authors: Hsu, Ching-Hsiang ; Chiang, Yi-Jen ; Yap, Chee

    Abstract | Document (2,177 KB) | BibTeX

    3-Manifold Triangulations with Small Treewidth
    Authors: Huszár, Kristóf ; Spreer, Jonathan

    Abstract | Document (885 KB) | BibTeX

    Algorithms for Metric Learning via Contrastive Embeddings
    Authors: Ihara, Diego ; Mohammadi, Neshat ; Sidiropoulos, Anastasios

    Abstract | Document (551 KB) | BibTeX

    Exact Computation of the Matching Distance on 2-Parameter Persistence Modules
    Authors: Kerber, Michael ; Lesnick, Michael ; Oudot, Steve

    Abstract | Document (461 KB) | BibTeX

    Probabilistic Smallest Enclosing Ball in High Dimensions via Subgradient Sampling
    Authors: Krivosija, Amer ; Munteanu, Alexander

    Abstract | Document (496 KB) | BibTeX

    A Weighted Approach to the Maximum Cardinality Bipartite Matching Problem with Applications in Geometric Settings
    Authors: Lahn, Nathaniel ; Raghvendra, Sharath

    Abstract | Document (493 KB) | BibTeX

    The Unbearable Hardness of Unknotting
    Authors: de Mesmay, Arnaud ; Rieck, Yo'av ; Sedgwick, Eric ; Tancer, Martin

    Abstract | Document (992 KB) | BibTeX

    On Grids in Point-Line Arrangements in the Plane
    Authors: Mirzaei, Mozhgan ; Suk, Andrew

    Abstract | Document (588 KB) | BibTeX

    On Weak epsilon-Nets and the Radon Number
    Authors: Moran, Shay ; Yehudayoff, Amir

    Abstract | Document (497 KB) | BibTeX

    Dynamic Planar Point Location in External Memory
    Authors: Munro, J. Ian ; Nekrich, Yakov

    Abstract | Document (656 KB) | BibTeX

    Efficient Algorithms for Ortho-Radial Graph Drawing
    Authors: Niedermann, Benjamin ; Rutter, Ignaz ; Wolf, Matthias

    Abstract | Document (1,392 KB) | BibTeX

    On the Chromatic Number of Disjointness Graphs of Curves
    Authors: Pach, János ; Tomon, István

    Abstract | Document (526 KB) | BibTeX

    Computing Persistent Homology of Flag Complexes via Strong Collapses
    Authors: Boissonnat, Jean-Daniel ; Pritam, Siddharth

    Abstract | Document (536 KB) | BibTeX

    Ham-Sandwich Cuts and Center Transversals in Subspaces
    Authors: Schnider, Patrick

    Abstract | Document (550 KB) | BibTeX

    Distribution-Sensitive Bounds on Relative Approximations of Geometric Ranges
    Authors: Tao, Yufei ; Wang, Yu

    Abstract | Document (543 KB) | BibTeX

    DTM-Based Filtrations
    Authors: Anai, Hirokazu ; Chazal, Frédéric ; Glisse, Marc ; Ike, Yuichi ; Inakoshi, Hiroya ; Tinarrage, Raphaël ; Umeda, Yuhei

    Abstract | Document (1,110 KB) | BibTeX

    A Divide-and-Conquer Algorithm for Two-Point L_1 Shortest Path Queries in Polygonal Domains
    Authors: Wang, Haitao

    Abstract | Document (609 KB) | BibTeX

    Near-Optimal Algorithms for Shortest Paths in Weighted Unit-Disk Graphs
    Authors: Wang, Haitao ; Xue, Jie

    Abstract | Document (577 KB) | BibTeX

    Searching for the Closest-Pair in a Query Translate
    Authors: Xue, Jie ; Li, Yuan ; Rahul, Saladi ; Janardan, Ravi

    Abstract | Document (643 KB) | BibTeX

    On the Complexity of the k-Level in Arrangements of Pseudoplanes
    Authors: Sharir, Micha ; Ziv, Chen

    Abstract | Document (1,486 KB) | BibTeX

    Packing Geometric Objects with Optimal Worst-Case Density (Multimedia Exposition)
    Authors: Becker, Aaron T. ; Fekete, Sándor P. ; Keldenich, Phillip ; Morr, Sebastian ; Scheffer, Christian

    Abstract | Document (1,530 KB) | BibTeX

    Properties of Minimal-Perimeter Polyominoes (Multimedia Exposition)
    Authors: Barequet, Gill ; Ben-Shachar, Gil

    Abstract | Document (395 KB) | BibTeX

    A Manual Comparison of Convex Hull Algorithms (Multimedia Exposition)
    Authors: Löffler, Maarten

    Abstract | Document (3,124 KB) | BibTeX

    Fréchet View - A Tool for Exploring Fréchet Distance Algorithms (Multimedia Exposition)
    Authors: Schäfer, Peter

    Abstract | Document (702 KB) | BibTeX

      




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