Portal - SoCG 2022

SoCG 2022	June 7-10, 2022, Berlin, Germany
38th International Symposium on Computational Geometry (SoCG 2022) Xavier Goaoc and Michael Kerber (Eds.)
ISBN 978-3-95977-227-3, LIPICS Vol. 224	ISSN 1868-8969

Additional Information

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

Authors

Bakke Bjerkevik, Håvard

Bjerkevik, Håvard Bakke

da Fonseca, Guilherme D.

Eskenazis, Alexandros

Fillmore, Christopher

Gonzalez-Lorenzo, Aldo

Kisfaludi‑Bak, Sándor

Papadopoulou, Evanthia

Raftopoulou, Chrysanthi N.

Raichel, Benjamin

Rasmussen, Peter M. R.

Sengupta, Akash Kumar

Spalding-Jamieson, Jack

Stefanou, Anastasios

Steiner, Raphael

Stephenson, Elizabeth

Weinberger, Alexandra

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Goaoc, Xavier ; Kerber, Michael

Abstract | Document (552 KB) | BibTeX

Tiling with Squares and Packing Dominos in Polynomial Time

Authors: Aamand, Anders ; Abrahamsen, Mikkel ; Ahle, Thomas ; Rasmussen, Peter M. R.

Abstract | Document (1,167 KB) | BibTeX

On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem

Authors: Afshani, Peyman ; de Berg, Mark ; Buchin, Kevin ; Gao, Jie ; Löffler, Maarten ; Nayyeri, Amir ; Raichel, Benjamin ; Sarkar, Rik ; Wang, Haotian ; Yang, Hao-Tsung

Abstract | Document (966 KB) | BibTeX

On Semialgebraic Range Reporting

Authors: Afshani, Peyman ; Cheng, Pingan

Abstract | Document (778 KB) | BibTeX

Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems

Authors: Agarwal, Pankaj K. ; Aronov, Boris ; Ezra, Esther ; Katz, Matthew J. ; Sharir, Micha

Abstract | Document (748 KB) | BibTeX

Twisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs

Authors: Aichholzer, Oswin ; García, Alfredo ; Tejel, Javier ; Vogtenhuber, Birgit ; Weinberger, Alexandra

Abstract | Document (1,812 KB) | BibTeX

Edge Partitions of Complete Geometric Graphs

Authors: Aichholzer, Oswin ; Obenaus, Johannes ; Orthaber, Joachim ; Paul, Rosna ; Schnider, Patrick ; Steiner, Raphael ; Taubner, Tim ; Vogtenhuber, Birgit

Abstract | Document (963 KB) | BibTeX

Minimum-Error Triangulations for Sea Surface Reconstruction

Authors: Arutyunova, Anna ; Driemel, Anne ; Haunert, Jan-Henrik ; Haverkort, Herman ; Kusche, Jürgen ; Langetepe, Elmar ; Mayer, Philip ; Mutzel, Petra ; Röglin, Heiko

Abstract | Document (1,929 KB) | BibTeX

Delaunay-Like Triangulation of Smooth Orientable Submanifolds by 𝓁₁-Norm Minimization

Authors: Attali, Dominique ; Lieutier, André

Abstract | Document (833 KB) | BibTeX

Tighter Bounds for Reconstruction from ε-Samples

Authors: Bakke Bjerkevik, Håvard

Abstract | Document (771 KB) | BibTeX

Erdős-Szekeres-Type Problems in the Real Projective Plane

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

Abstract | Document (903 KB) | BibTeX

True Contraction Decomposition and Almost ETH-Tight Bipartization for Unit-Disk Graphs

Authors: Bandyapadhyay, Sayan ; Lochet, William ; Lokshtanov, Daniel ; Saurabh, Saket ; Xue, Jie

Abstract | Document (905 KB) | BibTeX

Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds

Authors: Banyassady, Bahareh ; de Berg, Mark ; Bringmann, Karl ; Buchin, Kevin ; Fernau, Henning ; Halperin, Dan ; Kostitsyna, Irina ; Okamoto, Yoshio ; Slot, Stijn

Abstract | Document (991 KB) | BibTeX

Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures

Authors: Bartal, Yair ; Fandina, Ora Nova ; Larsen, Kasper Green

Abstract | Document (688 KB) | BibTeX

Quasi-Universality of Reeb Graph Distances

Authors: Bauer, Ulrich ; Bjerkevik, Håvard Bakke ; Fluhr, Benedikt

Abstract | Document (746 KB) | BibTeX

Gromov Hyperbolicity, Geodesic Defect, and Apparent Pairs in Vietoris-Rips Filtrations

Authors: Bauer, Ulrich ; Roll, Fabian

Abstract | Document (698 KB) | BibTeX

Acute Tours in the Plane

Authors: Biniaz, Ahmad

Abstract | Document (751 KB) | BibTeX

ETH-Tight Algorithms for Finding Surfaces in Simplicial Complexes of Bounded Treewidth

Authors: Black, Mitchell ; Blaser, Nello ; Nayyeri, Amir ; Vågset, Erlend Raa

Abstract | Document (1,293 KB) | BibTeX

Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes

Authors: Bonnet, Gilles ; Dadush, Daniel ; Grupel, Uri ; Huiberts, Sophie ; Livshyts, Galyna

Abstract | Document (743 KB) | BibTeX

Signed Barcodes for Multi-Parameter Persistence via Rank Decompositions

Authors: Botnan, Magnus Bakke ; Oppermann, Steffen ; Oudot, Steve

Abstract | Document (3,522 KB) | BibTeX

Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves

Authors: Bringmann, Karl ; Kisfaludi‑Bak, Sándor ; Künnemann, Marvin ; Marx, Dániel ; Nusser, André

Abstract | Document (929 KB) | BibTeX

Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs

Authors: Bringmann, Karl ; Kisfaludi‑Bak, Sándor ; Künnemann, Marvin ; Nusser, André ; Parsaeian, Zahra

Abstract | Document (854 KB) | BibTeX

Computing Continuous Dynamic Time Warping of Time Series in Polynomial Time

Authors: Buchin, Kevin ; Nusser, André ; Wong, Sampson

Abstract | Document (1,285 KB) | BibTeX

Long Plane Trees

Authors: Cabello, Sergio ; Hoffmann, Michael ; Klost, Katharina ; Mulzer, Wolfgang ; Tkadlec, Josef

Abstract | Document (1,207 KB) | BibTeX

The Universal 𝓁^p-Metric on Merge Trees

Authors: Cardona, Robert ; Curry, Justin ; Lam, Tung ; Lesnick, Michael

Abstract | Document (866 KB) | BibTeX

On Complexity of Computing Bottleneck and Lexicographic Optimal Cycles in a Homology Class

Authors: Chambers, Erin Wolf ; Parsa, Salman ; Schreiber, Hannah

Abstract | Document (1,161 KB) | BibTeX

Parameterized Algorithms for Upward Planarity

Authors: Chaplick, Steven ; Di Giacomo, Emilio ; Frati, Fabrizio ; Ganian, Robert ; Raftopoulou, Chrysanthi N. ; Simonov, Kirill

Abstract | Document (1,265 KB) | BibTeX

Finding Weakly Simple Closed Quasigeodesics on Polyhedral Spheres

Authors: Chartier, Jean ; de Mesmay, Arnaud

Abstract | Document (4,424 KB) | BibTeX

Tight Lower Bounds for Approximate & Exact k-Center in ℝ^d

Authors: Chitnis, Rajesh ; Saurabh, Nitin

Abstract | Document (855 KB) | BibTeX

Flat Folding an Unassigned Single-Vertex Complex (Combinatorially Embedded Planar Graph with Specified Edge Lengths) Without Flat Angles

Authors: Chung, Lily ; Demaine, Erik D. ; Hendrickson, Dylan ; Luo, Victor

Abstract | Document (1,179 KB) | BibTeX

Hop-Spanners for Geometric Intersection Graphs

Authors: Conroy, Jonathan B. ; Tóth, Csaba D.

Abstract | Document (941 KB) | BibTeX

Persistent Cup-Length

Authors: Contessoto, Marco ; Mémoli, Facundo ; Stefanou, Anastasios ; Zhou, Ling

Abstract | Document (1,032 KB) | BibTeX

Three-Chromatic Geometric Hypergraphs

Authors: Damásdi, Gábor ; Pálvölgyi, Dömötör

Abstract | Document (738 KB) | BibTeX

A Solution to Ringel’s Circle Problem

Authors: Davies, James ; Keller, Chaya ; Kleist, Linda ; Smorodinsky, Shakhar ; Walczak, Bartosz

Abstract | Document (943 KB) | BibTeX

Computing Generalized Rank Invariant for 2-Parameter Persistence Modules via Zigzag Persistence and Its Applications

Authors: Dey, Tamal K. ; Kim, Woojin ; Mémoli, Facundo

Abstract | Document (989 KB) | BibTeX

Tracking Dynamical Features via Continuation and Persistence

Authors: Dey, Tamal K. ; Lipiński, Michał ; Mrozek, Marian ; Slechta, Ryan

Abstract | Document (1,428 KB) | BibTeX

On the Discrete Fréchet Distance in a Graph

Authors: Driemel, Anne ; van der Hoog, Ivor ; Rotenberg, Eva

Abstract | Document (1,221 KB) | BibTeX

Computing a Link Diagram from Its Exterior

Authors: Dunfield, Nathan M. ; Obeidin, Malik ; Rudd, Cameron Gates

Abstract | Document (3,559 KB) | BibTeX

On Comparable Box Dimension

Authors: Dvořák, Zdeněk ; Gonçalves, Daniel ; Lahiri, Abhiruk ; Tan, Jane ; Ueckerdt, Torsten

Abstract | Document (645 KB) | BibTeX

Weak Coloring Numbers of Intersection Graphs

Authors: Dvořák, Zdeněk ; Pekárek, Jakub ; Ueckerdt, Torsten ; Yuditsky, Yelena

Abstract | Document (914 KB) | BibTeX

ε-Isometric Dimension Reduction for Incompressible Subsets of 𝓁_p

Authors: Eskenazis, Alexandros

Abstract | Document (814 KB) | BibTeX

Short Topological Decompositions of Non-Orientable Surfaces

Authors: Fuladi, Niloufar ; Hubard, Alfredo ; de Mesmay, Arnaud

Abstract | Document (4,871 KB) | BibTeX

Robust Radical Sylvester-Gallai Theorem for Quadratics

Authors: Garg, Abhibhav ; Oliveira, Rafael ; Sengupta, Akash Kumar

Abstract | Document (731 KB) | BibTeX

Robust Sylvester-Gallai Type Theorem for Quadratic Polynomials

Authors: Peleg, Shir ; Shpilka, Amir

Abstract | Document (720 KB) | BibTeX

Swap, Shift and Trim to Edge Collapse a Filtration

Authors: Glisse, Marc ; Pritam, Siddharth

Abstract | Document (1,124 KB) | BibTeX

Hardness and Approximation of Minimum Convex Partition

Authors: Grelier, Nicolas

Abstract | Document (637 KB) | BibTeX

Parameterised Partially-Predrawn Crossing Number

Authors: Hamm, Thekla ; Hliněný, Petr

Abstract | Document (1,200 KB) | BibTeX

Approximation Algorithms for Maximum Matchings in Geometric Intersection Graphs

Authors: Har-Peled, Sariel ; Yang, Everett

Abstract | Document (799 KB) | BibTeX

The Complexity of the Hausdorff Distance

Authors: Jungeblut, Paul ; Kleist, Linda ; Miltzow, Tillmann

Abstract | Document (1,401 KB) | BibTeX

Dynamic Connectivity in Disk Graphs

Authors: Kaplan, Haim ; Kauer, Alexander ; Klost, Katharina ; Knorr, Kristin ; Mulzer, Wolfgang ; Roditty, Liam ; Seiferth, Paul

Abstract | Document (1,270 KB) | BibTeX

An (ℵ₀,k+2)-Theorem for k-Transversals

Authors: Keller, Chaya ; Perles, Micha A.

Abstract | Document (812 KB) | BibTeX

Farthest-Point Voronoi Diagrams in the Presence of Rectangular Obstacles

Authors: Kim, Mincheol ; Seo, Chanyang ; Ahn, Taehoon ; Ahn, Hee-Kap

Abstract | Document (1,342 KB) | BibTeX

Point Separation and Obstacle Removal by Finding and Hitting Odd Cycles

Authors: Kumar, Neeraj ; Lokshtanov, Daniel ; Saurabh, Saket ; Suri, Subhash ; Xue, Jie

Abstract | Document (871 KB) | BibTeX

A Universal Triangulation for Flat Tori

Authors: Lazarus, Francis ; Tallerie, Florent

Abstract | Document (3,049 KB) | BibTeX

Sparse Euclidean Spanners with Tiny Diameter: A Tight Lower Bound

Authors: Le, Hung ; Milenković, Lazar ; Solomon, Shay

Abstract | Document (729 KB) | BibTeX

Minimum Height Drawings of Ordered Trees in Polynomial Time: Homotopy Height of Tree Duals

Authors: Ophelders, Tim ; Parsa, Salman

Abstract | Document (981 KB) | BibTeX

Disjointness Graphs of Short Polygonal Chains

Authors: Pach, János ; Tardos, Gábor ; Tóth, Géza

Abstract | Document (632 KB) | BibTeX

Covering Points by Hyperplanes and Related Problems

Authors: Patáková, Zuzana ; Sharir, Micha

Abstract | Document (592 KB) | BibTeX

The Degree-Rips Complexes of an Annulus with Outliers

Authors: Rolle, Alexander

Abstract | Document (866 KB) | BibTeX

Chains, Koch Chains, and Point Sets with Many Triangulations

Authors: Rutschmann, Daniel ; Wettstein, Manuel

Abstract | Document (697 KB) | BibTeX

Nearly-Doubling Spaces of Persistence Diagrams

Authors: Sheehy, Donald R. ; Sheth, Siddharth S.

Abstract | Document (804 KB) | BibTeX

From Geometry to Topology: Inverse Theorems for Distributed Persistence

Authors: Solomon, Elchanan ; Wagner, Alexander ; Bendich, Paul

Abstract | Document (1,014 KB) | BibTeX

A Positive Fraction Erdős-Szekeres Theorem and Its Applications

Authors: Suk, Andrew ; Zeng, Ji

Abstract | Document (831 KB) | BibTeX

Optimal Coreset for Gaussian Kernel Density Estimation

Authors: Tai, Wai Ming

Abstract | Document (731 KB) | BibTeX

GPU Computation of the Euler Characteristic Curve for Imaging Data

Authors: Wang, Fan ; Wagner, Hubert ; Chen, Chao

Abstract | Document (1,131 KB) | BibTeX

Space Ants: Episode II - Coordinating Connected Catoms (Media Exposition)

Authors: Bourgeois, Julien ; Fekete, Sándor P. ; Kosfeld, Ramin ; Kramer, Peter ; Piranda, Benoît ; Rieck, Christian ; Scheffer, Christian

Abstract | Document (2,524 KB) | BibTeX

A Cautionary Tale: Burning the Medial Axis Is Unstable (Media Exposition)

Authors: Chambers, Erin ; Fillmore, Christopher ; Stephenson, Elizabeth ; Wintraecken, Mathijs

Abstract | Document (17,169 KB) | BibTeX

Visualizing and Unfolding Nets of 4-Polytopes (Media Exposition)

Authors: Devadoss, Satyan L. ; Harvey, Matthew S. ; Zhang, Sam

Abstract | Document (861 KB) | BibTeX

Visualizing WSPDs and Their Applications (Media Exposition)

Authors: Ghosh, Anirban ; Shariful, FNU ; Wisnosky, David

Abstract | Document (546 KB) | BibTeX

Subdivision Methods for Sum-Of-Distances Problems: Fermat-Weber Point, n-Ellipses and the Min-Sum Cluster Voronoi Diagram (Media Exposition)

Authors: Mantas, Ioannis ; Papadopoulou, Evanthia ; Suderland, Martin ; Yap, Chee

Abstract | Document (4,167 KB) | BibTeX

An Interactive Framework for Reconfiguration in the Sliding Square Model (Media Exposition)

Authors: Sonke, Willem ; Wulms, Jules

Abstract | Document (778 KB) | BibTeX

Shadoks Approach to Minimum Partition into Plane Subgraphs (CG Challenge)

Authors: Crombez, Loïc ; da Fonseca, Guilherme D. ; Gerard, Yan ; Gonzalez-Lorenzo, Aldo

Abstract | Document (676 KB) | BibTeX

Conflict-Based Local Search for Minimum Partition into Plane Subgraphs (CG Challenge)

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

Abstract | Document (544 KB) | BibTeX

Local Search with Weighting Schemes for the CG:SHOP 2022 Competition (CG Challenge)

Authors: Fontan, Florian ; Lafourcade, Pascal ; Libralesso, Luc ; Momège, Benjamin

Abstract | Document (602 KB) | BibTeX

SAT-Based Local Search for Plane Subgraph Partitions (CG Challenge)

Authors: Schidler, André

Abstract | Document (4,305 KB) | BibTeX

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

38th International Symposium on Computational Geometry (SoCG 2022)