


default search action
41st SoCG 2025: Kanazawa, Japan
- Oswin Aichholzer
, Haitao Wang
:
41st International Symposium on Computational Geometry, SoCG 2025, June 23-27, 2025, Kanazawa, Japan. LIPIcs 332, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2025, ISBN 978-3-95977-370-6 - Front Matter, Table of Contents, Preface, Conference Organization. 0:i-0:xxii
- Mikkel Abrahamsen, Kevin Buchin, Maike Buchin, Linda Kleist, Maarten Löffler, Lena Schlipf, André Schulz, Jack Stade:
Reconfiguration of Unit Squares and Disks: PSPACE-Hardness in Simple Settings. 1:1-1:18 - Eyal Ackerman, Gábor Damásdi, Balázs Keszegh, Rom Pinchasi, Rebeka Raffay:
The Maximum Number of Digons Formed by Pairwise Intersecting Pseudocircles. 2:1-2:14 - Peyman Afshani, Yakov Nekrich, Frank Staals:
Convexity Helps Iterated Search in 3D. 3:1-3:14 - Pankaj K. Agarwal, Boris Aronov, Olivier Devillers, Christian Knauer, Guillaume Moroz:
A Subquadratic Algorithm for Computing the L₁-Distance Between Two Terrains. 4:1-4:17 - Pankaj K. Agarwal, Mark de Berg, Benjamin Holmgren, Alex Steiger, Martijn Struijs:
Optimal Motion Planning for Two Square Robots in a Rectilinear Environment. 5:1-5:17 - Ángel Javier Alonso:
A Sparse Multicover Bifiltration of Linear Size. 6:1-6:18 - Shinwoo An, Eunjin Oh, Jie Xue:
Single-Source Shortest Path Problem in Weighted Disk Graphs. 7:1-7:15 - Konrad Anand, Weiming Feng, Graham Freifeld, Heng Guo, Mark Jerrum, Jiaheng Wang:
Rapid Mixing of the Flip Chain over Non-Crossing Spanning Trees. 8:1-8:18 - Patrizio Angelini, Sabine Cornelsen, Carolina Haase, Michael Hoffmann, Eleni Katsanou, Fabrizio Montecchiani, Raphael Steiner, Antonios Symvonis:
Geometric Realizations of Dichotomous Ordinal Graphs. 9:1-9:16 - Dustin L. Arendt, Matthew Broussard, Bala Krishnamoorthy, Nathaniel Saul, Amber Thrall:
Steinhaus Filtration and Stable Paths in the Mapper. 10:1-10:21 - Dominique Attali, Mattéo Clémot, Bianca B. Dornelas, André Lieutier:
When Alpha-Complexes Collapse onto Codimension-1 Submanifolds. 11:1-11:19 - Sang Won Bae, Nicolau Oliver, Evanthia Papadopoulou:
Higher-Order Color Voronoi Diagrams and the Colorful Clarkson-Shor Framework. 12:1-12:19 - Jineon Baek, Martin Balko:
The Erdős-Szekeres Conjecture Revisited. 13:1-13:15 - Lies Beers, Magnus Bakke Botnan:
Extremal Betti Numbers and Persistence in Flag Complexes. 14:1-14:18 - Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, M. S. Ramanujan, Saket Saurabh:
When Distances Lie: Euclidean Embeddings in the Presence of Outliers and Distance Violations. 15:1-15:16 - Helena Bergold, Lukas Egeling, Hung P. Hoang:
Signotopes with Few Plus Signs. 16:1-16:14 - Sujoy Bhore, Timothy M. Chan, Zhengcheng Huang, Shakhar Smorodinsky, Csaba D. Tóth:
Sparse Bounded Hop-Spanners for Geometric Intersection Graphs. 17:1-17:15 - Therese Biedl, Éric Colin de Verdière, Fabrizio Frati, Anna Lubiw, Günter Rote:
Finding a Shortest Curve That Separates Few Objects from Many. 18:1-18:16 - Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari, Michiel Smid, Shakhar Smorodinsky, Milos Stojakovic:
Polychromatic Coloring of Tuples in Hypergraphs. 19:1-19:17 - Ahmad Biniaz, Anil Maheshwari, Magnus Christian Ring Merrild, Joseph S. B. Mitchell, Saeed Odak, Valentin Polishchuk, Eliot W. Robson, Casper Moldrup Rysgaard, Jens Kristian Refsgaard Schou, Thomas C. Shermer, Jack Spalding-Jamieson, Rolf Svenning, Da Wei Zheng:
Polynomial-Time Algorithms for Contiguous Art Gallery and Related Problems. 20:1-20:21 - Thomas Bläsius, Jean-Pierre von der Heydt, Sándor Kisfaludi-Bak, Marcus Wilhelm, Geert van Wordragen:
Structure and Independence in Hyperbolic Uniform Disk Graphs. 21:1-21:16 - Lotte Blank, Jacobus Conradi, Anne Driemel, Benedikt Kolbe, André Nusser, Marena Richter:
Transforming Dogs on the Line: On the Fréchet Distance Under Translation or Scaling in 1D. 22:1-22:16 - Édouard Bonnet, Kristóf Huszár:
On the Twin-Width of Smooth Manifolds. 23:1-23:16 - Édouard Bonnet, Pawel Rzazewski:
An 11/6-Approximation Algorithm for Vertex Cover on String Graphs. 24:1-24:15 - Karl Bringmann, Kasper Green Larsen, André Nusser, Eva Rotenberg, Yanheng Wang:
Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation. 25:1-25:16 - Kevin Buchin, Carolin Rehs, Torben Scheele:
Geometric Spanners of Bounded Tree-Width. 26:1-26:15 - Kevin Buchin, Antonia Kalb, Anil Maheshwari, Saeed Odak, Carolin Rehs, Michiel Smid, Sampson Wong:
Computing Oriented Spanners and Their Dilation. 27:1-27:17 - Rhuaidi Antonio Burke, Benjamin A. Burton, Jonathan Spreer:
Small Triangulations of 4-Manifolds and the 4-Manifold Census. 28:1-28:16 - Mathieu Carrière, Seunghyun Kim, Woojin Kim:
Sparsification of the Generalized Persistence Diagrams for Scalability Through Gradient Descent. 29:1-29:17 - Luca Castelli Aleardi, Éric Fusy, Jyh-Chwen Ko, Razvan-Stefan Puscasu:
Computation of Toroidal Schnyder Woods Made Simple and Fast: From Theory to Practice. 30:1-30:19 - Timothy M. Chan, Isaac M. Hair:
A Linear Time Algorithm for the Maximum Overlap of Two Convex Polygons Under Translation. 31:1-31:16 - Timothy M. Chan, Zhengcheng Huang:
Faster Algorithms for Reverse Shortest Path in Unit-Disk Graphs and Related Geometric Optimization Problems: Improving the Shrink-And-Bifurcate Technique. 32:1-32:14 - Timothy M. Chan, Chaya Keller, Shakhar Smorodinsky:
On Zarankiewicz's Problem for Intersection Hypergraphs of Geometric Objects. 33:1-33:14 - Siu-Wing Cheng, Haoqiang Huang, Le Jiang:
Simplification of Trajectory Streams. 34:1-34:14 - Oliver A. Chubet, Kirk P. Gardner, Donald R. Sheehy:
A Theory of Sub-Barcodes. 35:1-35:16 - James Davies, Agelos Georgakopoulos, Meike Hatzel, Rose McCarty:
Strongly Sublinear Separators and Bounded Asymptotic Dimension for Sphere Intersection Graphs. 36:1-36:16 - Sarita de Berg, Frank Staals:
Nearest Neighbor Searching in a Dynamic Simple Polygon. 37:1-37:15 - Colleen Delaney, Clément Maria, Eric Samperton:
An Algorithm for Tambara-Yamagami Quantum Invariants of 3-Manifolds, Parameterized by the First Betti Number. 38:1-38:15 - Erik D. Demaine, Stefan Langerman:
Tiling with Three Polygons Is Undecidable. 39:1-39:16 - Tamal K. Dey, Tao Hou, Dmitriy Morozov:
Apex Representatives. 40:1-40:16 - Tamal K. Dey, Jan Jendrysiak, Michael Kerber:
Decomposing Multiparameter Persistence Modules. 41:1-41:19 - Anne Driemel, Morteza Monemizadeh, Eunjin Oh, Frank Staals, David P. Woodruff:
Range Counting Oracles for Geometric Problems. 42:1-42:16 - Herbert Edelsbrunner, Alexey Garber, Morteza Saghafian:
On Spheres with k Points Inside. 43:1-43:12 - Eduard Eiben, Robert Ganian, Iyad Kanj, M. S. Ramanujan:
A Minor-Testing Approach for Coordinated Motion Planning with Sliding Robots. 44:1-44:15 - Marzieh Eidi, Sayan Mukherjee:
Higher Order Bipartiteness vs Bi-Partitioning in Simplicial Complexes. 45:1-45:12 - David Eppstein:
Non-Euclidean Erdős-Anning Theorems. 46:1-46:15 - Jeff Erickson, Christian Howard:
Shelling and Sinking Graphs on the Sphere. 47:1-47:18 - Sándor P. Fekete, Phillip Keldenich, Michael Perk:
Exact Algorithms for Minimum Dilation Triangulation. 48:1-48:18 - Arnold Filtser:
On Sparse Covers of Minor Free Graphs, Low Dimensional Metric Embeddings, and Other Applications. 49:1-49:16 - Jacob Fox, János Pach, Andrew Suk:
Immersions and Albertson's Conjecture. 50:1-50:10 - Shion Fukuzawa, Michael T. Goodrich, Sandy Irani:
Quantum Combine and Conquer and Its Applications to Sublinear Quantum Convex Hull and Maxima Set Construction. 51:1-51:15 - Abhibhav Garg, Rafael Oliveira, Akash Kumar Sengupta:
Uniform Bounds on Product Sylvester-Gallai Configurations. 52:1-52:15 - Benyamin Ghaseminia, Mohammad R. Salavatipour:
A PTAS for TSP with Neighbourhoods over Parallel Line Segments. 53:1-53:15 - Sariel Har-Peled, Benjamin Raichel, Eliot W. Robson:
The Fréchet Distance Unleashed: Approximating a Dog with a Frog. 54:1-54:13 - Alexander He, Eric Sedgwick, Jonathan Spreer:
A Practical Algorithm for Knot Factorisation. 55:1-55:15 - Martin G. Herold, Danupon Nanongkai, Joachim Spoerhase, Nithin Varma, Zihang Wu:
Sublinear Data Structures for Nearest Neighbor in Ultra High Dimensions. 56:1-56:15 - John Hershberger:
Snap Rounding: A Cautionary Tale. 57:1-57:14 - Tao Hou, Salman Parsa, Bei Wang:
Tracking the Persistence of Harmonic Chains: Barcode and Stability. 58:1-58:16 - John Iacono, Yakov Nekrich:
Incremental Planar Nearest Neighbor Queries with Optimal Query Time. 59:1-59:15 - Klaus Jansen, Debajyoti Kar, Arindam Khan, K. V. N. Sreenivas, Malte Tutas:
Improved Approximation Algorithms for Three-Dimensional Knapsack. 60:1-60:18 - Attila Jung, Dömötör Pálvölgyi:
k-Dimensional Transversals for Fat Convex Sets. 61:1-61:12 - Karthik C. S., Euiwoong Lee, Yuval Rabani, Chris Schwiegelshohn, Samson Zhou:
On Approximability of ℓ₂² Min-Sum Clustering. 62:1-62:18 - J. Mark Keil, Debajyoti Mondal:
The Maximum Clique Problem in a Disk Graph Made Easy. 63:1-63:16 - Donghan Kim, Woojin Kim, Wonjun Lee:
Super-Polynomial Growth of the Generalized Persistence Diagram. 64:1-64:20 - Yasuaki Kobayashi, Yuto Okada, Alexander Wolff:
Recognizing 2-Layer and Outer k-Planar Graphs. 65:1-65:16 - Corentin Lunel, Arnaud de Mesmay, Jonathan Spreer:
Hard Diagrams of Split Links. 67:1-67:17 - Dmitriy Morozov, Primoz Skraba:
Persistent (Co)Homology in Matrix Multiplication Time. 68:1-68:16 - Dmitriy Morozov, Luis Scoccola:
Computing Betti Tables and Minimal Presentations of Zero-Dimensional Persistent Homology. 69:1-69:15 - Tim Ophelders, Anna Schenfisch
, Willem Sonke, Bettina Speckmann:
Computing Geomorphologically Salient Networks via Discrete Morse Theory. 70:1-70:17 - Lara Ost, Sebastiano Cultrera di Montesano, Herbert Edelsbrunner:
Banana Trees for the Persistence in Time Series Experimentally. 71:1-71:13 - Sharath Raghvendra, Pouyan Shirzadian, Rachita Sowle:
Geometric Bipartite Matching Based Exact Algorithms for Server Problems. 72:1-72:15 - Thomas Schibler, Subhash Suri, Jie Xue:
Embedding Graphs as Euclidean kNN-Graphs. 73:1-73:14 - Jack Stade:
The Point-Boundary Art Gallery Problem Is ∃ℝ-Hard. 74:1-74:23 - Elizaveta Streltsova, Uli Wagner:
Levels in Arrangements: Linear Relations, the g-Matrix, and Applications to Crossing Numbers. 75:1-75:18 - Andrew Suk, Ethan Patrick White:
A Note on the No-(d+2)-On-a-Sphere Problem. 76:1-76:8 - Subhash Suri, Jie Xue, Xiongxin Yang, Jiumu Zhu:
Dynamic Maximum Depth of Geometric Objects. 77:1-77:13 - Ivor van der Hoog, Lara Ost, Eva Rotenberg, Daniel Rutschmann:
Efficient Greedy Discrete Subtrajectory Clustering. 78:1-78:20 - Mikkel Abrahamsen, Florestan Brunck, Jacobus Conradi, Benedikt Kolbe, André Nusser:
Computing Non-Obtuse Triangulations with Few Steiner Points (CG Challenge). 79:1-79:13 - Taehoon Ahn, Jaegun Lee, Byeonguk Kang, Hwi Kim:
Incremental Algorithm and Local Search for Minimum Non-Obtuse Triangulations (CG Challenge). 80:1-80:8 - Matthias Artmann, Tobias Maurer, Andreas Padalkin, Daniel Warner, Christian Scheideler:
AmoebotSim 2.0: A Visual Simulation Environment for the Amoebot Model with Reconfigurable Circuits and Joint Movements (Media Exposition). 81:1-81:5 - Hridhaan Banerjee, Carmen Isabel Day, Auguste H. Gezalyan, Olga Golovatskaia, Megan Hunleth, Sarah Hwang, Nithin Parepally, Lucy Wang, David M. Mount:
Software for the Thompson and Funk Polygonal Geometry (Media Exposition). 82:1-82:6 - Klint Faber, Auguste H. Gezalyan, Adam Martinson, Aniruddh Mutnuru, Nithin Parepally, Ryan Parker, Mihil Sreenilayam, Aram Zaprosyan, David M. Mount:
French Onion Soup, Ipelets for Points and Polygons (Media Exposition). 83:1-83:6 - Simon D. Fink, Dominik Peters:
Incremental and Interactive PQ- and PC-Trees (Media Exposition). 84:1-84:4 - UML Modular Robotics Group, Hugo A. Akitaya, Andrew Clements, Sam Downey, Jonathan Eisenbies, Soham Samanta, Gabriel Shahrouzi, Frederick Stock:
Finding Shortest Reconfiguration Sequences for Modular Robots (Media Exposition). 85:1-85:5

manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.