Computational Geometry Papers

Min-1-Planarity is NP-Hard Yuto Okada arxiv.org/abs/2605.14834 [𝚌𝚜.𝙲𝙶 𝚌𝚜.𝙳𝚂]

Hitting Axis-Parallel Segments with Weighted Points Rajiv Raman, Siddhartha Sarkar, Jatin Yadav arxiv.org/abs/2605.14499 [𝚌𝚜.𝙲𝙶 𝚌𝚜.𝙳𝚂]

Towards Scalable Persistence-Based Topological Optimization Abderrahim Bendahi, Alexandre Duplessis, Arnaud Fickinger arxiv.org/abs/2605.10996 [𝚌𝚜.𝙲𝙶 𝚌𝚜.𝙰𝙸 𝚌𝚜.𝙶𝚁 𝚖𝚊𝚝𝚑.𝙾𝙲]

Charting the Diameter Computation Landscape on Intersection Graphs in the Plane Timothy M. Chan, Hsien-Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, Hung Le, Da Wei Zheng arxiv.org/abs/2605.10692 [𝚌𝚜.𝙲𝙶]

Higher-order Persistence Diagrams Charles Fanning, Mehmet Aktas arxiv.org/abs/2605.09866 [𝚌𝚜.𝙲𝙶 𝚖𝚊𝚝𝚑.𝙰𝚃 𝚖𝚊𝚝𝚑.𝙵𝙰]

Nearly-Tight Bounds for Vertical Decomposition in Three and Four Dimensions Pankaj K. Agarwal, Esther Ezra, Micha Sharir arxiv.org/abs/2605.09234 [𝚌𝚜.𝙲𝙶]

Touring a Sequence of Orthogonal Polygons Katrin Casel, Sándor Kisfaludi-Bak, Linda Kleist, Jeroen S. K. Lamme, Eunjin Oh, Yanheng Wang arxiv.org/abs/2605.07882 [𝚌𝚜.𝙲𝙶 𝚌𝚜.𝙳𝚂] 💬Accepted at ICALP 2026

Instance and Universally Optimal Bounds for Imprecise Pareto Fronts Sarita de Berg, Nynne Maria Foldager Bække, Frida Astrup Eriksen, Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann arxiv.org/abs/2605.07523 [𝚌𝚜.𝙲𝙶]

Scalable GPU Construction of 3D Voronoi and Power Diagrams Bernardo Taveira, Carl Lindström, Maryam Fatemi, Lars Hammarstrand, Fredrik Kahl arxiv.org/abs/2605.06408 [𝚌𝚜.𝙲𝙶]

A Constant-Factor Approximation for Continuous Dynamic Time Warping in 2D Kevin Buchin, Maike Buchin, Jan Erik Swiadek, Sampson Wong arxiv.org/abs/2605.05917 [𝚌𝚜.𝙲𝙶] 💬Appearing in ICALP 2026

On the Complexity of Minimum Riesz s-Energy Subset Selection in Euclidean and Ultrametric Spaces Michael T. M. Emmerich, Ksenia Pereverdieva, André Deutz arxiv.org/abs/2605.04715 [𝚌𝚜.𝙲𝙶 𝚌𝚜.𝙲𝙲 𝚖𝚊𝚝𝚑.𝙾𝙲]

Optimally Covering Large Triangles with Homothetic Unit Triangles John M. Boyer arxiv.org/abs/2605.04111 [𝚌𝚜.𝙲𝙶]

Computing Planar Convex Hulls with a Promise Sepideh Aghamolaei, Kevin Buchin, Timothy M. Chan, Jacobus Conradi, Ivor Van der Hoog, Vahideh Keikha, Jeff M. Phillips, Benjamin Raichel arxiv.org/abs/2605.03904 [𝚌𝚜.𝙲𝙶]

Visibility Queries in Simple Polygons Sujoy Bhore, Chih-Hung Liu, Anurag Murty Naredla, Yakov Nekrich, Eunjin Oh, André van Renssen, Frank Staals, Haitao Wang, Jie Xue arxiv.org/abs/2605.03334 [𝚌𝚜.𝙲𝙶 𝚌𝚜.𝙳𝚂] 💬To appear in ICALP 2026

Manifold k-NN: Accelerated k-NN Queries for Manifold Point Clouds Pengfei Wang, Qinghao Guo, Haisen Zhao, Shiqing Xin, Shuangmin Chen, Changhe Tu, Wenping Wang arxiv.org/abs/2605.02224 [𝚌𝚜.𝙲𝙶 𝚌𝚜.𝙶𝚁]

A greedy maximal sweepline algorithm for a Jordan curve Apurva Mudgal arxiv.org/abs/2605.01861 [𝚌𝚜.𝙲𝙶]

Witness Set: A Visibility Problem in NP∩ XP Satyabrata Jana, Debabrata Pal, Bodhayan Roy, Sasanka Roy arxiv.org/abs/2605.01592 [𝚌𝚜.𝙲𝙶]

Spherical Geometrical Bases of Spherical Origami Takashi Yoshino arxiv.org/abs/2605.01184 [𝚌𝚜.𝙲𝙶 𝚌𝚜.𝙶𝚁]

Smallest Enclosing Disk Queries Using Farthest-Point Voronoi Diagrams Kevin Buchin, Mark Joachim Krallmann, Frank Staals arxiv.org/abs/2605.00743 [𝚌𝚜.𝙲𝙶 𝚌𝚜.𝙳𝚂]

Upward-Planar Drawings with Bounded Span Patrizio Angelini, Sabine Cornelsen, Giordano Da Lozzo, Fabrizio Frati, Philipp Kindermann, Ignaz Rutter, Johannes Zink arxiv.org/abs/2605.00603 [𝚌𝚜.𝙲𝙶 𝚌𝚜.𝙳𝚂]