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