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)

[11]  arXiv:2403.04905 [pdf, other]

Title: A Clique-Based Separator for Intersection Graphs of Geodesic Disks in $\mathbb{R}^2$

Authors: Boris Aronov, Mark de Berg, Leonidas Theocharous

Comments: The paper will appear in SoCG 2024

Subjects: Computational Geometry (cs.CG)

[12]  arXiv:2403.05697 [pdf, other]

Title: Dynamic Convex Hulls for Simple Paths

Authors: Bruce Brewer, Gerth Stølting Brodal, Haitao Wang

Comments: To appear in SoCG 2024

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

[13]  arXiv:2403.06211 [pdf, other]

Title: Solution-Hashing Search Based on Layout-Graph Transformation for Unequal Circle Packing

Authors: Jianrong Zhou, Jiyao He, Kun He

Subjects: Computational Geometry (cs.CG)

[14]  arXiv:2403.06494 [pdf, other]

Title: An Efficient Solution to the 2D Visibility Problem in Cartesian Grid Maps and its Application in Heuristic Path Planning

Authors: Ibrahim Ibrahim, Joris Gillis, Wilm Decré, Jan Swevers

Comments: 7 pages, 5 figures, IEEE ICRA 2024

Subjects: Computational Geometry (cs.CG); Graphics (cs.GR); Robotics (cs.RO)

[15]  arXiv:2403.06564 [pdf, other]

Title: An Algorithm for Correct Computation of Reeb Spaces for PL Bivariate Fields

Authors: Amit Chattopadhyay, Yashwanth Ramamurthi, Osamu Saeki

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

[16]  arXiv:2403.07200 [pdf, ps, other]

Title: Computing $p$-presentation distances is hard

Authors: Håvard Bakke Bjerkevik, Magnus Bakke Botnan

Comments: 28 pages, 7 figures

Subjects: Computational Geometry (cs.CG); Computational Complexity (cs.CC); Representation Theory (math.RT)

[17]  arXiv:2403.08977 [pdf, other]

Title: On maximum-sum matchings of bichromatic points

Authors: Oscar Chacón-Rivera, Pablo Pérez-Lantero

Subjects: Computational Geometry (cs.CG); Discrete Mathematics (cs.DM)

[18]  arXiv:2403.10033 [pdf, other]

Title: Ipelets for the Convex Polygonal Geometry

Authors: Nithin Parepally, Ainesh Chatterjee, Auguste Gezalyan, Hongyang Du, Sukrit Mangla, Kenny Wu, Sarah Hwang, David Mount

Subjects: Computational Geometry (cs.CG)

[19]  arXiv:2403.10204 [pdf, other]

Title: The Euclidean MST-ratio for Bi-colored Lattices

Authors: Sebastiano Cultrera di Montesano, Ondřej Draganov, Herbert Edelsbrunner, Morteza Saghafian

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

[20]  arXiv:2403.10311 [pdf, other]

Title: A canonical tree decomposition for order types, and some applications

Authors: Mathilde Bouvel, Valentin Féray, Xavier Goaoc, Florent Koechlin

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

[21]  arXiv:2403.11749 [pdf, other]

Title: Computing shortest closed curves on non-orientable surfaces

Authors: Denys Bulavka, Éric Colin de Verdière, Niloufar Fuladi

Comments: To appear at SoCG 2024

Subjects: Computational Geometry (cs.CG); Computational Complexity (cs.CC); Geometric Topology (math.GT)

[22]  arXiv:2403.11811 [pdf, ps, other]

Title: A Simple 2-Approximation Algorithm For Minimum Manhattan Network Problem

Authors: Md. Musfiqur Rahman Sanim, Safrunnesa Saira, Fatin Faiaz Ahsan, Rajon Bardhan, S.M. Ferdous

Comments: ARSSS International Conference, Dhaka, Bangladesh

Subjects: Computational Geometry (cs.CG); Computer Science and Game Theory (cs.GT)

[23]  arXiv:2403.11861 [pdf, other]

Title: Robustly Guarding Polygons

Authors: Rathish Das, Omrit Filtser, Matthew J. Katz, Joseph S.B. Mitchell

Comments: To appear in SoCG 2024

Subjects: Computational Geometry (cs.CG)

[24]  arXiv:2403.12276 [pdf, ps, other]

Title: Semi-Algebraic Off-line Range Searching and Biclique Partitions in the Plane

Authors: Pankaj K. Agarwal, Esther Ezra, Micha Sharir

Subjects: Computational Geometry (cs.CG)

[25]  arXiv:2403.12303 [pdf, other]

Title: Semialgebraic Range Stabbing, Ray Shooting, and Intersection Counting in the Plane

Authors: Timothy M. Chan, Pingan Cheng, Da Wei Zheng

Comments: SOCG 2024

Subjects: Computational Geometry (cs.CG)