Computational Geometry

Authors and titles for cs.CG in Mar 2024

[1]  arXiv:2403.00737 [pdf, other]

Title: Happy Ending: An Empty Hexagon in Every Set of 30 Points

Authors: Marijn J.H. Heule, Manfred Scheucher

Subjects: Computational Geometry (cs.CG); Logic in Computer Science (cs.LO); Combinatorics (math.CO)

[2]  arXiv:2403.01327 [pdf, ps, other]

Title: Euclidean distance compression via deep random features

Authors: Brett Leroux, Luis Rademacher

Subjects: Computational Geometry (cs.CG); Data Structures and Algorithms (cs.DS)

[3]  arXiv:2403.01354 [pdf, other]

Title: An Overview of Minimum Convex Cover and Maximum Hidden Set

Authors: Reilly Browne

Subjects: Computational Geometry (cs.CG)

[4]  arXiv:2403.02071 [pdf, other]

Title: On Efficient Approximation of the Maximum Distance to A Point Over an Intersection of Balls

Authors: Beniamin Costandin, Marius Costandin

Subjects: Computational Geometry (cs.CG); Optimization and Control (math.OC)

[5]  arXiv:2403.02627 [pdf, other]

Title: Eight-Partitioning Points in 3D, and Efficiently Too

Authors: Boris Aronov, Abdul Basit, Indu Ramesh, Gianluca Tasinato, Uli Wagner

Comments: 22 pages, 3 figures, preliminary version to appear in SoCG'24

Subjects: Computational Geometry (cs.CG); Combinatorics (math.CO)

[6]  arXiv:2403.02971 [pdf, ps, other]

Title: Space Complexity of Euclidean Clustering

Authors: Xiaoyi Zhu, Yuxiang Tian, Lingxiao Huang, Zengfeng Huang

Comments: Accepted by SoCG2024

Subjects: Computational Geometry (cs.CG); Data Structures and Algorithms (cs.DS)

[7]  arXiv:2403.03290 [pdf, ps, other]

Title: Maintaining Light Spanners via Minimal Updates

Authors: Hadi Khodabandeh, David Eppstein

Subjects: Computational Geometry (cs.CG); Data Structures and Algorithms (cs.DS)

[8]  arXiv:2403.03801 [pdf, other]

Title: Realizability of Rectangular Euler Diagrams

Authors: Dominik Dürrschnabel, Uta Priss

Comments: 16 pages, 5 figures, 2 algorithms

Subjects: Computational Geometry (cs.CG); Combinatorics (math.CO)

[9]  arXiv:2403.04356 [pdf, other]

Title: Fine-Grained Complexity of Earth Mover's Distance under Translation

Authors: Karl Bringmann, Frank Staals, Karol Węgrzycki, Geert van Wordragen

Comments: Full version of the paper "Fine-Grained Complexity of Earth Mover's Distance under Translation" accepted for SoCG 2024

Subjects: Computational Geometry (cs.CG)

[10]  arXiv:2403.04513 [pdf, other]

Title: A Coreset for Approximate Furthest-Neighbor Queries in a Simple Polygon

Authors: Mark de Berg, Leonidas Theocharous

Comments: To appear in SoCG 2024

Subjects: Computational Geometry (cs.CG)