Portal - SoCG 2023

SoCG 2023	June 12-15, 2023, Dallas, Texas, USA
39th International Symposium on Computational Geometry (SoCG 2023) Erin W. Chambers and Joachim Gudmundsson (Eds.)
ISBN 978-3-95977-273-0, LIPICS Vol. 258	ISSN 1868-8969

Additional Information

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

Authors

Bærentzen, J. Andreas

Bille Meyling, William

Christensen, Rasmus Emil

Chubet, Oliver A.

Clause, Nate

da Fonseca, Guilherme D.

Gæde, Emil Toftegaard

Montecchiani, Fabrizio

Naredla, Anurag Murty

Papadopoulou, Evanthia

Roos Hoefgeest, Pepijn

Schrezenmaier, Hendrik

Tralie, Christopher J.

Weinberger, Alexandra

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Chambers, Erin W. ; Gudmundsson, Joachim

Abstract | Document (519 KB) | BibTeX

Geometric Embeddability of Complexes Is ∃ℝ-Complete

Authors: Abrahamsen, Mikkel ; Kleist, Linda ; Miltzow, Tillmann

Abstract | Document (1,721 KB) | BibTeX

Distinguishing Classes of Intersection Graphs of Homothets or Similarities of Two Convex Disks

Authors: Abrahamsen, Mikkel ; Walczak, Bartosz

Abstract | Document (1,450 KB) | BibTeX

Lower Bounds for Intersection Reporting Among Flat Objects

Authors: Afshani, Peyman ; Cheng, Pingan

Abstract | Document (755 KB) | BibTeX

Computing Instance-Optimal Kernels in Two Dimensions

Authors: Agarwal, Pankaj K. ; Har-Peled, Sariel

Abstract | Document (1,133 KB) | BibTeX

Line Intersection Searching Amid Unit Balls in 3-Space

Authors: Agarwal, Pankaj K. ; Ezra, Esther

Abstract | Document (813 KB) | BibTeX

Drawings of Complete Multipartite Graphs up to Triangle Flips

Authors: Aichholzer, Oswin ; Chiu, Man-Kwun ; Hoang, Hung P. ; Hoffmann, Michael ; Kynčl, Jan ; Maus, Yannic ; Vogtenhuber, Birgit ; Weinberger, Alexandra

Abstract | Document (1,583 KB) | BibTeX

Decomposition of Zero-Dimensional Persistence Modules via Rooted Subsets

Authors: Alonso, Ángel Javier ; Kerber, Michael

Abstract | Document (857 KB) | BibTeX

On Helly Numbers of Exponential Lattices

Authors: Ambrus, Gergely ; Balko, Martin ; Frankl, Nóra ; Jung, Attila ; Naszódi, Márton

Abstract | Document (879 KB) | BibTeX

Optimal Volume-Sensitive Bounds for Polytope Approximation

Authors: Arya, Sunil ; Mount, David M.

Abstract | Document (1,127 KB) | BibTeX

Coresets for Clustering in Geometric Intersection Graphs

Authors: Bandyapadhyay, Sayan ; Fomin, Fedor V. ; Inamdar, Tanmay

Abstract | Document (905 KB) | BibTeX

Minimum-Membership Geometric Set Cover, Revisited

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

Abstract | Document (898 KB) | BibTeX

FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii

Authors: Bandyapadhyay, Sayan ; Lochet, William ; Saurabh, Saket

Abstract | Document (722 KB) | BibTeX

Multilevel Skeletonization Using Local Separators

Authors: Bærentzen, J. Andreas ; Christensen, Rasmus Emil ; Gæde, Emil Toftegaard ; Rotenberg, Eva

Abstract | Document (6,674 KB) | BibTeX

Efficient Computation of Image Persistence

Authors: Bauer, Ulrich ; Schmahl, Maximilian

Abstract | Document (746 KB) | BibTeX

Efficient Two-Parameter Persistence Computation via Cohomology

Authors: Bauer, Ulrich ; Lenzen, Fabian ; Lesnick, Michael

Abstract | Document (1,076 KB) | BibTeX

The Complexity of Geodesic Spanners

Authors: de Berg, Sarita ; van Kreveld, Marc ; Staals, Frank

Abstract | Document (773 KB) | BibTeX

An Extension Theorem for Signotopes

Authors: Bergold, Helena ; Felsner, Stefan ; Scheucher, Manfred

Abstract | Document (828 KB) | BibTeX

Extending Orthogonal Planar Graph Drawings Is Fixed-Parameter Tractable

Authors: Bhore, Sujoy ; Ganian, Robert ; Khazaliya, Liana ; Montecchiani, Fabrizio ; Nöllenburg, Martin

Abstract | Document (987 KB) | BibTeX

Improved Bounds for Covering Paths and Trees in the Plane

Authors: Biniaz, Ahmad

Abstract | Document (951 KB) | BibTeX

Sparse Higher Order Čech Filtrations

Authors: Buchet, Mickaël ; B. Dornelas, Bianca ; Kerber, Michael

Abstract | Document (865 KB) | BibTeX

Finding Large Counterexamples by Selectively Exploring the Pachner Graph

Authors: Burton, Benjamin A. ; He, Alexander

Abstract | Document (842 KB) | BibTeX

Improved Algebraic Degeneracy Testing

Authors: Cardinal, Jean ; Sharir, Micha

Abstract | Document (840 KB) | BibTeX

Constant-Hop Spanners for More Geometric Intersection Graphs, with Even Smaller Size

Authors: Chan, Timothy M. ; Huang, Zhengcheng

Abstract | Document (1,171 KB) | BibTeX

Minimum L_∞ Hausdorff Distance of Point Sets Under Translation: Generalizing Klee’s Measure Problem

Authors: Chan, Timothy M.

Abstract | Document (748 KB) | BibTeX

Meta-Diagrams for 2-Parameter Persistence

Authors: Clause, Nate ; Dey, Tamal K. ; Mémoli, Facundo ; Wang, Bei

Abstract | Document (876 KB) | BibTeX

Algorithms for Length Spectra of Combinatorial Tori

Authors: Delecroix, Vincent ; Ebbens, Matthijs ; Lazarus, Francis ; Yakovlev, Ivan

Abstract | Document (745 KB) | BibTeX

Computing a Dirichlet Domain for a Hyperbolic Surface

Authors: Despré, Vincent ; Kolbe, Benedikt ; Parlier, Hugo ; Teillaud, Monique

Abstract | Document (1,247 KB) | BibTeX

The Parameterized Complexity of Coordinated Motion Planning

Authors: Eiben, Eduard ; Ganian, Robert ; Kanj, Iyad

Abstract | Document (2,104 KB) | BibTeX

Non-Crossing Hamiltonian Paths and Cycles in Output-Polynomial Time

Authors: Eppstein, David

Abstract | Document (851 KB) | BibTeX

Finding a Maximum Clique in a Disk Graph

Authors: Espenant, Jared ; Keil, J. Mark ; Mondal, Debajyoti

Abstract | Document (1,379 KB) | BibTeX

Linear Size Universal Point Sets for Classes of Planar Graphs

Authors: Felsner, Stefan ; Schrezenmaier, Hendrik ; Schröder, Felix ; Steiner, Raphael

Abstract | Document (858 KB) | BibTeX

When Ternary Triangulated Disc Packings Are Densest: Examples, Counter-Examples and Techniques

Authors: Fernique, Thomas ; Pchelina, Daria

Abstract | Document (1,405 KB) | BibTeX

Labeled Nearest Neighbor Search and Metric Spanners via Locality Sensitive Orderings

Authors: Filtser, Arnold

Abstract | Document (983 KB) | BibTeX

Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs

Authors: Galby, Esther ; Munaro, Andrea ; Yang, Shizhou

Abstract | Document (849 KB) | BibTeX

Voronoi Diagrams in the Hilbert Metric

Authors: Gezalyan, Auguste H. ; Mount, David M.

Abstract | Document (1,138 KB) | BibTeX

Combinatorial Designs Meet Hypercliques: Higher Lower Bounds for Klee’s Measure Problem and Related Problems in Dimensions d ≥ 4

Authors: Gorbachev, Egor ; Künnemann, Marvin

Abstract | Document (720 KB) | BibTeX

A Generalization of the Persistent Laplacian to Simplicial Maps

Authors: Gülen, Aziz Burak ; Mémoli, Facundo ; Wan, Zhengchao ; Wang, Yusu

Abstract | Document (745 KB) | BibTeX

The Christoffel-Darboux Kernel for Topological Data Analysis

Authors: Roos Hoefgeest, Pepijn ; Slot, Lucas

Abstract | Document (2,712 KB) | BibTeX

The Number of Edges in Maximal 2-Planar Graphs

Authors: Hoffmann, Michael ; M. Reddy, Meghana

Abstract | Document (829 KB) | BibTeX

Worst-Case Deterministic Fully-Dynamic Biconnectivity in Changeable Planar Embeddings

Authors: Holm, Jacob ; van der Hoog, Ivor ; Rotenberg, Eva

Abstract | Document (1,220 KB) | BibTeX

Disjoint Faces in Drawings of the Complete Graph and Topological Heilbronn Problems

Authors: Hubard, Alfredo ; Suk, Andrew

Abstract | Document (951 KB) | BibTeX

On the Width of Complicated JSJ Decompositions

Authors: Huszár, Kristóf ; Spreer, Jonathan

Abstract | Document (3,552 KB) | BibTeX

Reconfiguration of Colorings in Triangulations of the Sphere

Authors: Ito, Takehiro ; Iwamasa, Yuni ; Kobayashi, Yusuke ; Maezawa, Shun-ichi ; Nozaki, Yuta ; Okamoto, Yoshio ; Ozeki, Kenta

Abstract | Document (1,165 KB) | BibTeX

On the Geometric Thickness of 2-Degenerate Graphs

Authors: Jain, Rahul ; Ricci, Marco ; Rollin, Jonathan ; Schulz, André

Abstract | Document (1,308 KB) | BibTeX

The Localized Union-Of-Balls Bifiltration

Authors: Kerber, Michael ; Söls, Matthias

Abstract | Document (864 KB) | BibTeX

Online and Dynamic Algorithms for Geometric Set Cover and Hitting Set

Authors: Khan, Arindam ; Lonkar, Aditya ; Rahul, Saladi ; Subramanian, Aditya ; Wiese, Andreas

Abstract | Document (1,391 KB) | BibTeX

Sparse Euclidean Spanners with Optimal Diameter: A General and Robust Lower Bound via a Concave Inverse-Ackermann Function

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

Abstract | Document (780 KB) | BibTeX

Shortest Paths in Portalgons

Authors: Löffler, Maarten ; Ophelders, Tim ; Silveira, Rodrigo I. ; Staals, Frank

Abstract | Document (4,886 KB) | BibTeX

The Geodesic Edge Center of a Simple Polygon

Authors: Lubiw, Anna ; Naredla, Anurag Murty

Abstract | Document (842 KB) | BibTeX

A Structural Approach to Tree Decompositions of Knots and Spatial Graphs

Authors: Lunel, Corentin ; de Mesmay, Arnaud

Abstract | Document (695 KB) | BibTeX

Ephemeral Persistence Features and the Stability of Filtered Chain Complexes

Authors: Mémoli, Facundo ; Zhou, Ling

Abstract | Document (878 KB) | BibTeX

Abstract Voronoi-Like Graphs: Extending Delaunay’s Theorem and Applications

Authors: Papadopoulou, Evanthia

Abstract | Document (1,108 KB) | BibTeX

Random Projections for Curves in High Dimensions

Authors: Psarros, Ioannis ; Rohde, Dennis

Abstract | Document (710 KB) | BibTeX

New Approximation Algorithms for Touring Regions

Authors: Qi, Benjamin ; Qi, Richard

Abstract | Document (835 KB) | BibTeX

Combinatorial Depth Measures for Hyperplane Arrangements

Authors: Schnider, Patrick ; Soberón, Pablo

Abstract | Document (695 KB) | BibTeX

FibeRed: Fiberwise Dimensionality Reduction of Topologically Complex Data with Vector Bundles

Authors: Scoccola, Luis ; Perea, Jose A.

Abstract | Document (3,222 KB) | BibTeX

Toroidal Coordinates: Decorrelating Circular Coordinates with Lattice Reduction

Authors: Scoccola, Luis ; Gakhar, Hitesh ; Bush, Johnathan ; Schonsheck, Nikolas ; Rask, Tatum ; Zhou, Ling ; Perea, Jose A.

Abstract | Document (6,733 KB) | BibTeX

Topological Universality of the Art Gallery Problem

Authors: Stade, Jack ; Tucker-Foltz, Jamie

Abstract | Document (1,218 KB) | BibTeX

On Higher Dimensional Point Sets in General Position

Authors: Suk, Andrew ; Zeng, Ji

Abstract | Document (662 KB) | BibTeX

Slice, Simplify and Stitch: Topology-Preserving Simplification Scheme for Massive Voxel Data

Authors: Wagner, Hubert

Abstract | Document (1,084 KB) | BibTeX

Maximum Overlap Area of a Convex Polyhedron and a Convex Polygon Under Translation

Authors: Zhu, Honglin ; Kweon, Hyuk Jun

Abstract | Document (806 KB) | BibTeX

Godzilla Onions: A Skit and Applet to Explain Euclidean Half-Plane Fractional Cascading (Media Exposition)

Authors: Berger, Richard ; Ha, Vincent ; Kratz, David ; Lin, Michael ; Moyer, Jeremy ; Tralie, Christopher J.

Abstract | Document (493 KB) | BibTeX

Interactive 2D Periodic Graphs (Media Exposition)

Authors: Camero, Alexandra ; Streinu, Ileana

Abstract | Document (1,271 KB) | BibTeX

Greedy Permutations and Finite Voronoi Diagrams (Media Exposition)

Authors: Chubet, Oliver A. ; Macnichol, Paul ; Parikh, Parth ; Sheehy, Donald R. ; Sheth, Siddharth S.

Abstract | Document (1,084 KB) | BibTeX

The Sum of Squares in Polycubes (Media Exposition)

Authors: Sheehy, Donald R.

Abstract | Document (3,518 KB) | BibTeX

Constructing Concise Convex Covers via Clique Covers (CG Challenge)

Authors: Abrahamsen, Mikkel ; Bille Meyling, William ; Nusser, André

Abstract | Document (1,918 KB) | BibTeX

Shadoks Approach to Convex Covering (CG Challenge)

Authors: da Fonseca, Guilherme D.

Abstract | Document (953 KB) | BibTeX

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

39th International Symposium on Computational Geometry (SoCG 2023)