Accepted Papers

36th SoCG - Zürich, Switzerland - June 23-26, 2020

• Jean-Daniel Boissonnat and Mathijs Wintraecken. The topological correctness of the PL-approximations of isomanifolds
• Martin Balko, Manfred Scheucher and Pavel Valtr. Holes and islands in random point sets
• Sándor Fekete, Utkarsh Gupta, Phillip Keldenich, Christian Scheffer and Sahil Shah. Worst-Case Optimal Covering of Rectangles by Disks
• Nello Blaser and Morten Brun. Relative persistent homology
• Sergey Avvakumov and Gabriel Nivasch. Homotopic Curve Shortening and the Affine Curve-Shortening flow
• Sariel Har-Peled and Mitchell Jones. Fast Algorithms for Geometric Consensuses
• Haitao Wang. On the Planar Two-Center Problem and Circular Hulls
• David Cohen-Steiner, André Lieutier and Julien Vuillamy. Lexicographic optimal homologous chains and applications to point cloud triangulations
• Erik D. Demaine, Adam Hesterberg and Jason S. Ku. Finding Closed Quasigeodesics on Convex Polyhedra
• Kevin A. Buchin, Valentin Polishchuk, Leonid Sedov and Roman Voronov. Geometric secluded paths and planar satisfiability
• Clément Maria, Steve Oudot and Yitzchak Solomon. Intrinsic Topological Transforms via the Distance Kernel Embedding
• Simon Zhang, Mengbai Xiao and Hao Wang. GPU-Accelerated Computation of Vietoris-Rips Barcodes
• Boris Aronov, Esther Ezra and Micha Sharir. Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets
• Noga Alon, Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky and Yelena Yuditsky. The Epsilon-t-Net Problem
• Alan Arroyo, Julien Bensmail and R. Bruce Richter. Extending Drawings of Graphs to Arrangements of Pseudolines
• Boris Aronov, Mark de Berg, Joachim Gudmundsson and Michael Horton. On beta-plurality points in spatial voting games
• Aruni Choudhary and Wolfgang Mulzer. No-dimensional Tverberg Theorems and Algorithms
• Vadim Lebovici, Steve Oudot and Magnus Botnan. On rectangle-decomposable persistence bimodules
• Henk Alkema, Mark de Berg and Sándor Kisfaludi-Bak. Euclidean TSP in Narrow Strips
• Emo Welzl and Uli Wagner. Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips)
• Emo Welzl and Xavier Goaoc. Convex hulls of random order types
• Sándor Kisfaludi-Bak. A quasi-polynomial algorithm for well-spaced hyperbolic TSP
• Eyal Ackerman, Balázs Keszegh and Günter Rote. An almost optimal bound on the number of intersections of two simple polygons
• Sang Won Bae and Sang Duk Yoon. Empty Squares in Arbitrary Orientation among Points
• Haitao Wang. Algorithms for Subpath Convex Hull Queries and Ray-Shooting among Segments
• Sándor Fekete, Linda Kleist and Dominik Krupke. Minimum Scan Cover with Angular Transition Costs
• Tamal Dey, Tianqi Li and Yusu Wang. An efficient algorithm for 1-st (persistent) path homology
• Monika Henzinger, Stefan Neumann and Andreas Wiese. Dynamic Approximate Maximum Independent Set in Interval and Geometric Intersection Graphs
• Claire Brécheteau. Robust anisotropic power-functions-based filtrations for clustering.
• Michael Dennis, Ljubomir Perkovic and Duru Türkoğlu. The Stretch Factor of Hexagon-Delaunay Triangulations
• Zuzana Patáková, Martin Tancer and Uli Wagner. Barycentric cuts through a convex body
• Kyle Fox and Jiashuai Lu. A near-linear time approximation scheme for geometric transportation with arbitrary supplies and spread
• Siu-Wing Cheng, Man-Kwun Chiu, Kai Jin and Man Ting Wong. A Generalization of Self-Improving Algorithms
• Siu-Wing Cheng and Man Kit Lau. Dynamic Distribution-Sensitive Point Location
• Vincent Despré, Jean-Marc Schlenker and Monique Teillaud. Flipping Geometric Triangulations on Hyperbolic Surfaces
• Oleg Zlydenko and Micha Sharir. Incidences between points and curves with almost two degrees of freedom
• Jacob Fox, Janos Pach and Andrew Suk. Bounded VC-dimension implies the Schur-Erdos conjecture
• Jeff Phillips and Pingfan Tang. Sketched MinDist
• Safwa Ameer, Matt Gibson, Erik Krohn, Sean Soderman and Qing Wang. Terrain Visibility Graphs: Persistence is Not Enough
• Shreya Arya, Jean-Daniel Boissonnat and Kunal Dutta. Dimensionality Reduction for $k$-Distance Applied to Persistent Homology
• Nora Frankl, Tamas Hubai and Domotor Palvolgyi. Almost-monochromatic sets and the chromatic number of the plane
• Nora Frankl and Andrey Kupavskii. Almost sharp bounds on the number of chains in the plane
• William Maxwell, Glencora Borradaile and Amir Nayyeri. Minimum bounded chains and minimum homologous chains in embedded simplicial complexes
• Orit E. Raz and Jozsef Solymosi. Dense graphs have rigid parts
• Akanksha Agrawal, Kristine Knudsen, Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi. The Parameterized Complexity of Guarding Almost Convex Polygons
• Talha Bin Masood, Tathagata Ray and Vijay Natarajan. Parallel Computation of Alpha Complex for Biomolecules
• Michael Bekos, Giordano Da Lozzo, Svenja Griesbach, Martin Gronemann, Fabrizio Montecchiani and Chrysanthi Raftopoulou. Book Embeddings of Nonplanar Graphs with Small Faces in Few Pages
• Michael Kerber and Arnur Nigmetov. Efficient Approximation of the Matching Distance for 2-parameter persistence
• Ulrich Bauer, Claudia Landi and Facundo Memoli. The Reeb Graph Edit Distance is Universal
• Jeff Erickson and Patrick Lin. A Toroidal Maxwell-Cremona-Delaunay Correspondence
• Wolfgang Mulzer and Pavel Valtr. Long Alternating Paths Exist
• Abhishek Rathod. Fast Algorithms for Minimum Cycle Basis and Minimum Homology Basis
• Jean-Daniel Boissonnat and Siddharth Pritam. Edge Collapse and Persistence of Flag Complexes.
• Tamal Dey, Marian Mrozek and Ryan Slechta. Persistence of the Conley Index in Combinatorial Dynamical Systems
• Guenther Eder, Martin Held and Peter Palfrader. On Implementing Straight Skeletons: Challenges and Experiences
• Zuzana Patáková. Bounding Radon's number via Betti numbers
• Chen Cai, Woojin Kim, Yusu Wang and Facundo Memoli. Elder-rule-staircodes for augmented metric spaces
• Rami Vanguri, Mathieu Carriere, Chao Chen, Andrew Aukerman, Kevin Gardner and Raul Rabadan. Persistent Homology Based Characterization of the Breast Cancer Immune Microenvironment: A Feasibility Study
• Eduard Eiben and Daniel Lokshtanov. Removing Connected Obstacles in the Plane is FPT
• Haim Kaplan, Micha Sharir and Uri Stemmer. How to Compute a Point in the Convex Hull Privately and Efficiently?
• Abhinandan Nath and Erin Taylor. Clustering trajectories in near-linear time, and point sets in polynomial time
• Timothy M. Chan, Qizheng He and Yakov Nekrich. Further Results on Colored Range Searching
• Timothy M. Chan and Qizheng He. Faster Approximation Algorithms for Geometric Set Cover
• Yakov Nekrich. Four-Dimensional Dominance Range Reporting in Linear Space
• Pankaj K. Agarwal, Hsien-Chih Chang, Subhash Suri, Allen Xiao and Jie Xue. Dynamic geometric set cover and hitting set
• Parker Evans, Brittany Terese Fasy and Carola Wenk. Combinatorial Properties of Self-Overlapping Curves and Interior Boundaries
• Jisu Kim, Jaehyeok Shin, Frederic Chazal, Alessandro Rinaldo and Larry Wasserman. Homotopy Reconstruction via the Cech Complex and the Rips Complex
• Benjamin A. Burton. The next 350 million knots
• Fedor Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh and Meirav Zehavi. ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs
• Dömötör Pálvölgyi. Radon numbers grow linearly