Portal - SoCG 2020

SoCG 2020	June 23-26, 2020, Zürich, Switzerland
36th International Symposium on Computational Geometry (SoCG 2020) Sergio Cabello and Danny Z. Chen (Eds.)
ISBN 978-3-95977-143-6, LIPICS Vol. 164	ISSN 1868-8969

Additional Information

License
Conference Website
Complete volume (PDF, 91 MB)
Search Publication Server

Authors

Boissonnat, Jean-Daniel

Fasy, Brittany Terese

Kisfaludi-Bak, Sándor

Kleist, Linda

Knudsen, Kristine V. K.

Montecchiani, Fabrizio

Raftopoulou, Chrysanthi

Spalding-Jamieson, Jack

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Cabello, Sergio ; Chen, Danny Z.

Abstract | Document (358 KB) | BibTeX

An Almost Optimal Bound on the Number of Intersections of Two Simple Polygons

Authors: Ackerman, Eyal ; Keszegh, Balázs ; Rote, Günter

Abstract | Document (1,315 KB) | BibTeX

Dynamic Geometric Set Cover and Hitting Set

Authors: Agarwal, Pankaj K. ; Chang, Hsien-Chih ; Suri, Subhash ; Xiao, Allen ; Xue, Jie

Abstract | Document (597 KB) | BibTeX

The Parameterized Complexity of Guarding Almost Convex Polygons

Authors: Agrawal, Akanksha ; Knudsen, Kristine V. K. ; Lokshtanov, Daniel ; Saurabh, Saket ; Zehavi, Meirav

Abstract | Document (1,491 KB) | BibTeX

Euclidean TSP in Narrow Strips

Authors: Alkema, Henk ; de Berg, Mark ; Kisfaludi-Bak, Sándor

Abstract | Document (912 KB) | BibTeX

The ε-t-Net Problem

Authors: Alon, Noga ; Jartoux, Bruno ; Keller, Chaya ; Smorodinsky, Shakhar ; Yuditsky, Yelena

Abstract | Document (507 KB) | BibTeX

Terrain Visibility Graphs: Persistence Is Not Enough

Authors: Ameer, Safwa ; Gibson-Lopez, Matt ; Krohn, Erik ; Soderman, Sean ; Wang, Qing

Abstract | Document (543 KB) | BibTeX

On β-Plurality Points in Spatial Voting Games

Authors: Aronov, Boris ; de Berg, Mark ; Gudmundsson, Joachim ; Horton, Michael

Abstract | Document (822 KB) | BibTeX

Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets

Authors: Aronov, Boris ; Ezra, Esther ; Sharir, Micha

Abstract | Document (489 KB) | BibTeX

Extending Drawings of Graphs to Arrangements of Pseudolines

Authors: Arroyo, Alan ; Bensmail, Julien ; Richter, R. Bruce

Abstract | Document (579 KB) | BibTeX

Dimensionality Reduction for k-Distance Applied to Persistent Homology

Authors: Arya, Shreya ; Boissonnat, Jean-Daniel ; Dutta, Kunal ; Lotz, Martin

Abstract | Document (484 KB) | BibTeX

Persistent Homology Based Characterization of the Breast Cancer Immune Microenvironment: A Feasibility Study

Authors: Aukerman, Andrew ; Carrière, Mathieu ; Chen, Chao ; Gardner, Kevin ; Rabadán, Raúl ; Vanguri, Rami

Abstract | Document (3,530 KB) | BibTeX

Homotopic Curve Shortening and the Affine Curve-Shortening Flow

Authors: Avvakumov, Sergey ; Nivasch, Gabriel

Abstract | Document (562 KB) | BibTeX

Empty Squares in Arbitrary Orientation Among Points

Authors: Bae, Sang Won ; Yoon, Sang Duk

Abstract | Document (777 KB) | BibTeX

Holes and Islands in Random Point Sets

Authors: Balko, Martin ; Scheucher, Manfred ; Valtr, Pavel

Abstract | Document (726 KB) | BibTeX

The Reeb Graph Edit Distance Is Universal

Authors: Bauer, Ulrich ; Landi, Claudia ; Mémoli, Facundo

Abstract | Document (471 KB) | BibTeX

Book Embeddings of Nonplanar Graphs with Small Faces in Few Pages

Authors: Bekos, Michael A. ; Da Lozzo, Giordano ; Griesbach, Svenja M. ; Gronemann, Martin ; Montecchiani, Fabrizio ; Raftopoulou, Chrysanthi

Abstract | Document (1,024 KB) | BibTeX

Parallel Computation of Alpha Complexes for Biomolecules

Authors: Masood, Talha Bin ; Ray, Tathagata ; Natarajan, Vijay

Abstract | Document (1,928 KB) | BibTeX

Relative Persistent Homology

Authors: Blaser, Nello ; Brun, Morten

Abstract | Document (390 KB) | BibTeX

Edge Collapse and Persistence of Flag Complexes

Authors: Boissonnat, Jean-Daniel ; Pritam, Siddharth

Abstract | Document (537 KB) | BibTeX

The Topological Correctness of PL-Approximations of Isomanifolds

Authors: Boissonnat, Jean-Daniel ; Wintraecken, Mathijs

Abstract | Document (986 KB) | BibTeX

Minimum Bounded Chains and Minimum Homologous Chains in Embedded Simplicial Complexes

Authors: Borradaile, Glencora ; Maxwell, William ; Nayyeri, Amir

Abstract | Document (529 KB) | BibTeX

On Rectangle-Decomposable 2-Parameter Persistence Modules

Authors: Botnan, Magnus Bakke ; Lebovici, Vadim ; Oudot, Steve

Abstract | Document (567 KB) | BibTeX

Robust Anisotropic Power-Functions-Based Filtrations for Clustering

Authors: Brécheteau, Claire

Abstract | Document (1,152 KB) | BibTeX

Geometric Secluded Paths and Planar Satisfiability

Authors: Buchin, Kevin ; Polishchuk, Valentin ; Sedov, Leonid ; Voronov, Roman

Abstract | Document (876 KB) | BibTeX

The Next 350 Million Knots

Authors: Burton, Benjamin A.

Abstract | Document (1,896 KB) | BibTeX

Elder-Rule-Staircodes for Augmented Metric Spaces

Authors: Cai, Chen ; Kim, Woojin ; Mémoli, Facundo ; Wang, Yusu

Abstract | Document (994 KB) | BibTeX

Faster Approximation Algorithms for Geometric Set Cover

Authors: Chan, Timothy M. ; He, Qizheng

Abstract | Document (481 KB) | BibTeX

Further Results on Colored Range Searching

Authors: Chan, Timothy M. ; He, Qizheng ; Nekrich, Yakov

Abstract | Document (444 KB) | BibTeX

A Generalization of Self-Improving Algorithms

Authors: Cheng, Siu-Wing ; Chiu, Man-Kwun ; Jin, Kai ; Wong, Man Ting

Abstract | Document (484 KB) | BibTeX

Dynamic Distribution-Sensitive Point Location

Authors: Cheng, Siu-Wing ; Lau, Man-Kit

Abstract | Document (470 KB) | BibTeX

No-Dimensional Tverberg Theorems and Algorithms

Authors: Choudhary, Aruni ; Mulzer, Wolfgang

Abstract | Document (506 KB) | BibTeX

Lexicographic Optimal Homologous Chains and Applications to Point Cloud Triangulations

Authors: Cohen-Steiner, David ; Lieutier, André ; Vuillamy, Julien

Abstract | Document (3,138 KB) | BibTeX

Finding Closed Quasigeodesics on Convex Polyhedra

Authors: Demaine, Erik D. ; Hesterberg, Adam C. ; Ku, Jason S.

Abstract | Document (684 KB) | BibTeX

The Stretch Factor of Hexagon-Delaunay Triangulations

Authors: Dennis, Michael ; Perković, Ljubomir ; Türkoğlu, Duru

Abstract | Document (599 KB) | BibTeX

Flipping Geometric Triangulations on Hyperbolic Surfaces

Authors: Despré, Vincent ; Schlenker, Jean-Marc ; Teillaud, Monique

Abstract | Document (770 KB) | BibTeX

An Efficient Algorithm for 1-Dimensional (Persistent) Path Homology

Authors: Dey, Tamal K. ; Li, Tianqi ; Wang, Yusu

Abstract | Document (861 KB) | BibTeX

Persistence of the Conley Index in Combinatorial Dynamical Systems

Authors: Dey, Tamal K. ; Mrozek, Marian ; Slechta, Ryan

Abstract | Document (4,146 KB) | BibTeX

On Implementing Straight Skeletons: Challenges and Experiences

Authors: Eder, Günther ; Held, Martin ; Palfrader, Peter

Abstract | Document (1,781 KB) | BibTeX

Removing Connected Obstacles in the Plane Is FPT

Authors: Eiben, Eduard ; Lokshtanov, Daniel

Abstract | Document (878 KB) | BibTeX

A Toroidal Maxwell-Cremona-Delaunay Correspondence

Authors: Erickson, Jeff ; Lin, Patrick

Abstract | Document (862 KB) | BibTeX

Combinatorial Properties of Self-Overlapping Curves and Interior Boundaries

Authors: Evans, Parker ; Fasy, Brittany Terese ; Wenk, Carola

Abstract | Document (1,172 KB) | BibTeX

Worst-Case Optimal Covering of Rectangles by Disks

Authors: Fekete, Sándor P. ; Gupta, Utkarsh ; Keldenich, Phillip ; Scheffer, Christian ; Shah, Sahil

Abstract | Document (3,556 KB) | BibTeX

Minimum Scan Cover with Angular Transition Costs

Authors: Fekete, Sándor P. ; Kleist, Linda ; Krupke, Dominik

Abstract | Document (2,752 KB) | BibTeX

ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs

Authors: Fomin, Fedor V. ; Lokshtanov, Daniel ; Panolan, Fahad ; Saurabh, Saket ; Zehavi, Meirav

Abstract | Document (682 KB) | BibTeX

A Near-Linear Time Approximation Scheme for Geometric Transportation with Arbitrary Supplies and Spread

Authors: Fox, Kyle ; Lu, Jiashuai

Abstract | Document (617 KB) | BibTeX

Bounded VC-Dimension Implies the Schur-Erdős Conjecture

Authors: Fox, Jacob ; Pach, János ; Suk, Andrew

Abstract | Document (437 KB) | BibTeX

Almost-Monochromatic Sets and the Chromatic Number of the Plane

Authors: Frankl, Nóra ; Hubai, Tamás ; Pálvölgyi, Dömötör

Abstract | Document (569 KB) | BibTeX

Almost Sharp Bounds on the Number of Discrete Chains in the Plane

Authors: Frankl, Nóra ; Kupavskii, Andrey

Abstract | Document (563 KB) | BibTeX

Convex Hulls of Random Order Types

Authors: Goaoc, Xavier ; Welzl, Emo

Abstract | Document (599 KB) | BibTeX

Fast Algorithms for Geometric Consensuses

Authors: Har-Peled, Sariel ; Jones, Mitchell

Abstract | Document (3,600 KB) | BibTeX

Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles

Authors: Henzinger, Monika ; Neumann, Stefan ; Wiese, Andreas

Abstract | Document (488 KB) | BibTeX

How to Find a Point in the Convex Hull Privately

Authors: Kaplan, Haim ; Sharir, Micha ; Stemmer, Uri

Abstract | Document (534 KB) | BibTeX

Efficient Approximation of the Matching Distance for 2-Parameter Persistence

Authors: Kerber, Michael ; Nigmetov, Arnur

Abstract | Document (553 KB) | BibTeX

Homotopy Reconstruction via the Cech Complex and the Vietoris-Rips Complex

Authors: Kim, Jisu ; Shin, Jaehyeok ; Chazal, Frédéric ; Rinaldo, Alessandro ; Wasserman, Larry

Abstract | Document (680 KB) | BibTeX

A Quasi-Polynomial Algorithm for Well-Spaced Hyperbolic TSP

Authors: Kisfaludi-Bak, Sándor

Abstract | Document (698 KB) | BibTeX

Intrinsic Topological Transforms via the Distance Kernel Embedding

Authors: Maria, Clément ; Oudot, Steve ; Solomon, Elchanan

Abstract | Document (572 KB) | BibTeX

Long Alternating Paths Exist

Authors: Mulzer, Wolfgang ; Valtr, Pavel

Abstract | Document (621 KB) | BibTeX

k-Median Clustering Under Discrete Fréchet and Hausdorff Distances

Authors: Nath, Abhinandan ; Taylor, Erin

Abstract | Document (618 KB) | BibTeX

Four-Dimensional Dominance Range Reporting in Linear Space

Authors: Nekrich, Yakov

Abstract | Document (475 KB) | BibTeX

Radon Numbers Grow Linearly

Authors: Pálvölgyi, Dömötör

Abstract | Document (394 KB) | BibTeX

Bounding Radon Number via Betti Numbers

Authors: Patáková, Zuzana

Abstract | Document (630 KB) | BibTeX

Barycentric Cuts Through a Convex Body

Authors: Patáková, Zuzana ; Tancer, Martin ; Wagner, Uli

Abstract | Document (733 KB) | BibTeX

Sketched MinDist

Authors: Phillips, Jeff M. ; Tang, Pingfan

Abstract | Document (1,014 KB) | BibTeX

Fast Algorithms for Minimum Cycle Basis and Minimum Homology Basis

Authors: Rathod, Abhishek

Abstract | Document (546 KB) | BibTeX

Dense Graphs Have Rigid Parts

Authors: Raz, Orit E. ; Solymosi, József

Abstract | Document (538 KB) | BibTeX

Incidences Between Points and Curves with Almost Two Degrees of Freedom

Authors: Sharir, Micha ; Zlydenko, Oleg

Abstract | Document (493 KB) | BibTeX

Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips)

Authors: Wagner, Uli ; Welzl, Emo

Abstract | Document (775 KB) | BibTeX

On the Planar Two-Center Problem and Circular Hulls

Authors: Wang, Haitao

Abstract | Document (611 KB) | BibTeX

Algorithms for Subpath Convex Hull Queries and Ray-Shooting Among Segments

Authors: Wang, Haitao

Abstract | Document (492 KB) | BibTeX

GPU-Accelerated Computation of Vietoris-Rips Persistence Barcodes

Authors: Zhang, Simon ; Xiao, Mengbai ; Wang, Hao

Abstract | Document (1,184 KB) | BibTeX

The Spiroplot App (Media Exposition)

Authors: van Dommelen, Casper ; van Kreveld, Marc ; Urhausen, Jérôme

Abstract | Document (1,443 KB) | BibTeX

Coordinated Particle Relocation with Global Signals and Local Friction (Media Exposition)

Authors: Baez, Victor M. ; Becker, Aaron T. ; Fekete, Sándor P. ; Schmidt, Arne

Abstract | Document (1,857 KB) | BibTeX

Space Ants: Constructing and Reconfiguring Large-Scale Structures with Finite Automata (Media Exposition)

Authors: Abdel-Rahman, Amira ; Becker, Aaron T. ; Biediger, Daniel E. ; Cheung, Kenneth C. ; Fekete, Sándor P. ; Gershenfeld, Neil A. ; Hugo, Sabrina ; Jenett, Benjamin ; Keldenich, Phillip ; Niehs, Eike ; Rieck, Christian ; Schmidt, Arne ; Scheffer, Christian ; Yannuzzi, Michael

Abstract | Document (5,685 KB) | BibTeX

How to Make a CG Video (Media Exposition)

Authors: Becker, Aaron T. ; Fekete, Sándor P.

Abstract | Document (12,279 KB) | BibTeX

Covering Rectangles by Disks: The Video (Media Exposition)

Authors: Fekete, Sándor P. ; Keldenich, Phillip ; Scheffer, Christian

Abstract | Document (859 KB) | BibTeX

Step-By-Step Straight Skeletons (Media Exposition)

Authors: Eder, Günther ; Held, Martin ; Palfrader, Peter

Abstract | Document (457 KB) | BibTeX

Computing Animations of Linkages with Rotational Symmetry (Media Exposition)

Authors: Dewar, Sean ; Grasegger, Georg ; Legerský, Jan

Abstract | Document (379 KB) | BibTeX

Hiding Sliding Cubes: Why Reconfiguring Modular Robots Is Not Easy (Media Exposition)

Authors: Miltzow, Tillmann ; Parada, Irene ; Sonke, Willem ; Speckmann, Bettina ; Wulms, Jules

Abstract | Document (3,575 KB) | BibTeX

Dots & Polygons (Media Exposition)

Authors: Buchin, Kevin ; Hagedoorn, Mart ; Kostitsyna, Irina ; van Mulken, Max ; Rensen, Jolan ; van Schooten, Leo

Abstract | Document (500 KB) | BibTeX

Designing Art Galleries (Media Exposition)

Authors: van Benthem, Toon ; Buchin, Kevin ; Kostitsyna, Irina ; Slot, Stijn

Abstract | Document (603 KB) | BibTeX

Plane-Filling Trails (Media Exposition)

Authors: Haverkort, Herman

Abstract | Document (4,678 KB) | BibTeX

Visual Demo of Discrete Stratified Morse Theory (Media Exposition)

Authors: Zhou, Youjia ; Knudson, Kevin ; Wang, Bei

Abstract | Document (855 KB) | BibTeX

Computing Low-Cost Convex Partitions for Planar Point Sets with Randomized Local Search and Constraint Programming (CG Challenge)

Authors: Zheng, Da Wei ; Spalding-Jamieson, Jack ; Zhang, Brandon

Abstract | Document (1,935 KB) | BibTeX

Computing Low-Cost Convex Partitions for Planar Point Sets Based on a Memetic Approach (CG Challenge)

Authors: Moalic, Laurent ; Schmitt, Dominique ; Lepagnot, Julien ; Kritter, Julien

Abstract | Document (1,217 KB) | BibTeX

Computing Low-Cost Convex Partitions for Planar Point Sets Based on Tailored Decompositions (CG Challenge)

Authors: Eder, Günther ; Held, Martin ; de Lorenzo, Stefan ; Palfrader, Peter

Abstract | Document (1,034 KB) | BibTeX

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

36th International Symposium on Computational Geometry (SoCG 2020)