Portal - SoCG 2019

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

Boissonnat, Jean-Daniel

Chaudhury, Bhaskar Ray

Colin de Verdière, Éric

Edelsbrunner, Herbert

Madathil, Jayakrishnan

Sidiropoulos, Anastasios

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

35th International Symposium on Computational Geometry (SoCG 2019)