The SoCG-logo
Call for Papers: 40th SoCG - June Tue. 11 - Fri. 14, 2024

The 40th International Symposium on Computational Geometry (SoCG 2024) is planned to be held in Athens, Greece, June 11–14 2024, as part of the Computational Geometry (CG) Week. We invite high quality submissions that describe original research on computational problems in a geometric and/or topological setting. Topics of interest include, but are not limited to:

Important Dates
SoCG 2024 Conference Webpage
SoCG 2024 HotCRP Submission Webpage
Code of conduct

SoCG is dedicated to providing an environment that is free from harassment, bullying, discrimination, and retaliation for all participants. All attendees, speakers, sponsors, and volunteers at our conference are required to agree with the CG Week code of conduct.

A person found in violation of these standards can be barred from attendance. This includes violations and sanctions that were established by other academic or professional institutions as the outcome of a formal enquiry.

If an author has a conflict of such nature with a potential reviewer, and the author has sufficient grounds to believe that the review would be negatively biased, then the author is asked to declare this conflict in HotCRP. You are also welcome to contact a SoCG SafeTOC advocate who will treat any supporting information confidentially. For a list of SoCG advocates with contact information, please refer to CG Week Code of Conduct.

Submission Guidelines
Accepted Papers
Program Committee
List of Accepted Papers
Title Authors
1 An $O(n \log n)$-Time Approximation Scheme for Geometric Many-to-Many Matching Sayan Bandyapadhyay and Jie Xue
2 Topological k-metrics Willow Barkan, Huck Bennett, and Amir Nayyeri
3 Polychromatic Colorings of Geometric Hypergraphs via Shallow Hitting Sets Tim Planken and Torsten Ueckerdt
4 Beyond chromatic threshold via $(p,q)$-theorem, and blow-up phenomenon Hong Liu, Chong Shangguan, Jozef Skokan, and Zixiang Xu
5 Map-Matching Queries Under Fréchet Distance on Low-Density Spanners Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Aleksandr Popov, and Sampson Wong
6 Discrete Fréchet Distance Oracles Boris Aronov, Tsuri Farhana, Matthew J. Katz, and Indu Ramesh
7 Fast approximations and coresets for $(k,\ell)$-median under dynamic time warping Jacobus Conradi, Benedikt Kolbe, Ioannis Psarros, and Dennis Rohde
8 A GPU algorithm for enumerating seed PL-spheres of Picard number 4 whose facets are bases of a binary matroid and application to toric topology Suyoung Choi, Hyeontae Jang, and Mathieu Vallée
9 Totally geodesic surfaces in hyperbolic 3-manifolds: algorithms and examples Brannon Basilio, Chaeryn Lee, and Joseph Malionek
10 Effective Computation of the Heegaard Genus of 3-Manifolds Benjamin A. Burton and Finn Thompson
11 Hopf Arborescent Links, Minor Theory, and Decidability of the Genus Defect Pierre Dehornoy, Corentin Lunel, and Arnaud de Mesmay
12 Pach's animal problem within the bounding box Martin Tancer
13 Reconfiguration of plane trees in convex geometric graphs Nicolas Bousquet, Lucas De Meyer, Théo Pierron, and Alexandra Wesolek
14 On the Parameterized Complexity of Motion Planning for Rectangular Robots Iyad Kanj and Salman Parsa
15 A Universal In-Place Reconfiguration Algorithm for Sliding Cube-Shaped Robots in Quadratic Time Zachary Abel, Hugo Akitaya, Scott Kominers, Matias Korman, and Frederick Stock
16 Almost Optimal Locality Sensitive Orderings in Euclidean Space Zhimeng Gao and Sariel Har-Peled
17 A Quadtree, a Steiner Spanner, and Approximate Nearest Neighbours in Hyperbolic Space Sándor Kisfaludi-Bak and Geert van Wordragen
18 Optimal Euclidean Tree Covers Hsien-Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenković, Shay Solomon, and Cuong Than
19 Discrepancy of halfplanes Manasseh Ahmed, Tsun-Ming Cheung, Hamed Hatami, and Kusha Sareen
20 A Canonical Tree Decomposition for Chirotopes Mathilde Bouvel, Valentin Feray, Xavier Goaoc, and Florent Koechlin
21 Saturation results around the Erdős-Szekeres problem Gábor Damásdi, Zichao Dong, Manfred Scheucher, and Ji Zeng
22 A Clique-Based Separator for Intersection Graphs of Geodesic Disks in $\mathbb{R}^2$ Boris Aronov, Mark de Berg, and Leonidas Theocharous
23 ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs Shinwoo An and Eunjin Oh
24 Computing Diameter+2 in Truly-Subquadratic Time for Unit-Disk Graphs Hsien-Chih Chang, Jie Gao, and Hung Le
25 Stability and Approximations for Decorated Reeb Spaces Justin Curry, Washington Mio, Tom Needham, Osman Berat Okutan, and Florian Russold
26 Strange Random Topology of the Circle Uzu Lim
27 On Edge Collapse of Random Simplicial Complexes Jean-Daniel Boissonnat, Kunal Dutta, Soumik Dutta, and Siddharth Pritam
28 Moderate Dimension Reduction for $k$-Center Clustering Shaofeng H.-C. Jiang, Robert Krauthgamer, and Shay Sapir
29 Dimensionality of Hamming metrics and Rademacher type Alexandros Eskenazis
30 Space Complexity of Euclidean Clustering Xiaoyi Zhu, Yuxiang Tian, Lingxiao Huang, and Zengfeng Huang
31 Clustering with Few Disks to Minimize the Sum of Radii Mikkel Abrahamsen, Sarita de Berg, Lucas Meijer, André Nusser, and Leonidas Theocharous
32 An Improved Lower Bound on the Number of Pseudoline Arrangements [merged] Fernando Cortés Kühnast, Justin Dallant, Stefan Felsner, and Manfred Scheucher
33 On the number of digons in arrangements of pairwise intersecting circles Eyal Ackerman, Gábor Damásdi, Balázs Keszegh, Rom Pinchasi, and Rebeka Blanka Raffay
34 A structure theorem for pseudo-segments and its applications Jacob Fox, Janos Pach, and Andrew Suk
35 Sweeping Arrangements of Non-Piercing Curves in Plane Suryendu Dalal, Rahul Gangopadhyay, Rajiv Raman, and Saurabh Ray
36 Dynamic Convex Hulls for Simple Paths Bruce Brewer, Gerth Stølting Brodal, and Haitao Wang
37 Optimal Algorithm for the Planar Two-Center Problem Kyungjin Cho, Eunjin Oh, Haitao Wang, and Jie Xue
38 Geometric matching and bottleneck problems Sergio Cabello, Siu-Wing Cheng, Otfried Cheong, and Christian Knauer
39 Convex Polygon Containment: Improving Quadratic to Near Linear Time Timothy M. Chan and Isaac M. Hair
40 Computing shortest closed curves on non-orientable surfaces Denys Bulavka, Éric Colin de Verdière, and Niloufar Fuladi
41 Cup Product Persistence and Its Efficient Computation Tamal K. Dey and Abhishek Rathod
42 Efficient Algorithms for Complexes of Persistence Modules with Applications Tamal K. Dey, Florian Russold, and Shreyas N. Samaga
43 Computing Zigzag Vineyard Efficiently Including Expansions and Contractions Tamal K. Dey and Tao Hou
44 Fréchet Edit Distance Emily Fox, Amir Nayyeri, Jonathan James Perry, and Benjamin Raichel
45 Fine-Grained Complexity of Earth Mover's Distance under Translation Karl Bringmann, Frank Staals, Karol Wegrzycki, and Geert van Wordragen
46 Faster Fréchet Distance Approximation through Truncated Smoothing Thijs van der Horst and Tim Ophelders
47 Morse Theory for the k-NN Distance Function Yohai Reani and Omer Bobrowski
48 Approximating Multiplicatively Weighted Voronoi Diagrams: Efficient Construction with Linear Size Joachim Gudmundsson, Martin P. Seybold, and Sampson Wong
49 Light, Reliable Spanners Arnold Filtser, Yuval Gitlitz, and Ofer Neiman
50 Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain Sarita de Berg, Till Miltzow, and Frank Staals
51 A Coreset for Approximate Furthest-Neighbor Queries in a Simple Polygon Mark de Berg and Leonidas Theocharous
52 Robustly Guarding Polygons Rathish Das, Omrit Filtser, Matthew J. Katz, and Joseph Mitchell
53 Approximating the Maximum Independent Set of Convex Polygons with a Bounded Number of Directions Fabrizio Grandoni, Edin Husić, Mathieu Mari, and Antoine Tinguely
54 Semialgebraic Range Stabbing, Ray Shooting, and Intersection Counting in the Plane Timothy M. Chan, Pingan Cheng, and Da Wei Zheng
55 Off-line Semi-Algebraic Range Searching in the Plane Pankaj K Agarwal, Esther Ezra, and Micha Sharir
56 An improved bound on sums of square roots via the subspace theorem Friedrich Eisenbrand, Matthieu Haeberle, and Neta Singer
57 A Topological Version of Schaefer’s Dichotomy Theorem Patrick Schnider and Simon Weber
58 Approximating the geometric knapsack problem in near-linear time and dynamically Moritz Buchem, Paul Deuker, and Andreas Wiese
59 Faster Approximation Scheme for Euclidean $k$-TSP Ernest van Wijland and Hang Zhou
60 Plane Hamiltonian cycles in convex drawings Helena Bergold, Stefan Felsner, Meghana M. Reddy, Joachim Orthaber, and Manfred Scheucher
61 Constrained and Ordered Level Planarity Parameterized by the Number of Levels Václav Blažej, Boris Klemz, Felix Klesen, Marie Diana Sieper, Alexander Wolff, and Johannes Zink
62 8-Partitioning Points in 3D, and Efficiently Too Boris Aronov, Abdul Basit, Indu Ramesh, Gianluca Tasinato, and Uli Wagner
63 Grid Peeling of Parabolas Günter Rote, Moritz Rüber, and Morteza Saghafian
64 Nearly Orthogonal Sets over Finite Fields Dror Chawin and Ishay Haviv
65 Colorful intersections and Tverberg partitions Michael Gene Dobbins, Andreas F. Holmsen, and Dohyeon Lee
66 Dynamic Geometric Connectivity in the Plane with Constant Query Time Timothy M. Chan and Zhengcheng Huang
67 Fully Dynamic Maximum Independent Sets of Disks in Polylogarithmic Update Time Sujoy Bhore, Martin Nöllenburg, Csaba D. Tóth, and Jules Wulms
68 Zarankiewicz's Problem via $\epsilon$-t-Nets Chaya Keller and Shakhar Smorodinsky
69 Probabilistic Analysis of Multiparameter Persistence Decompositions into Intervals Ángel Javier Alonso, Michael Kerber, and Primoz Skraba
70 Measure Theoretic Reeb Graphs and Reeb Spaces Qingsong Wang, Guanqun Ma, Raghavendra Sridharamurthy, and Bei Wang
71 Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger for subsets of Euclidean spaces and of Riemannian manifolds Dominique Attali, Hana Dal Poz Kourimska, Christopher Fillmore, Ishika Ghosh, André Lieutier, Elizabeth Stephenson, and Mathijs Wintraecken
72 Separator Theorem and Algorithms for Planar Hyperbolic Graphs Sándor Kisfaludi-Bak, Jana Masaříková, Erik Jan van Leeuwen, Bartosz Walczak, and Karol Węgrzycki
73 A 1.9999-Approximation Algorithm for Vertex Cover on String Graphs Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi
74 Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern Jacob Focke, Florian Hoersch, Shaohua Li, and Dániel Marx
75 Demystifying Latschev's Theorem: Manifold Reconstruction from Noisy Data Sushovan Majhi
76 Wrapping Cycles in Delaunay Complexes: Bridging Persistent Homology and Discrete Morse Theory Ulrich Bauer and Fabian Roll
77 The medial axis of closed bounded sets is Lipschitz stable with respect to the Hausdorff distance under ambient diffeomorphisms Hana Dal Poz Kourimska, André Lieutier, and Mathijs Wintraecken
78 Practical Software for Triangulating and Simplifying 4-Manifolds Rhuaidi Burke
79 Algorithms for Halfplane Coverage and Related Problems Haitao Wang and Jie Xue
80 Enclosing Points with Geometric Objects Timothy Chan, Qizheng He, and Jie Xue
81 SCARST: Schnyder Compact And Regularity Sensitive Triangulation Data Structure Luca Castelli Aleardi and Olivier Devillers
82 Maximum Betti Numbers of Čech Complexes Herbert Edelsbrunner and Janos Pach