:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Hoffmann, Michael, Miltzow, Tillmann, Weber, Simon, Wulf, Lasse
Format:	Preprint
Published:	2024
Subjects:	Computational Geometry
Online Access:	https://arxiv.org/abs/2401.02172
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Framework for $\exists \mathbb{R}$-Completeness of Two-Dimensional Packing Problems
by: Abrahamsen, Mikkel, et al.
Published: (2020)

Training Fully Connected Neural Networks is $\exists\mathbb{R}$-Complete
by: Bertschinger, Daniel, et al.
Published: (2022)

Geometric Thickness of Multigraphs is $\exists \mathbb{R}$-complete
by: Förster, Henry, et al.
Published: (2023)

Beyond Bits: An Introduction to Computation over the Reals
by: Miltzow, Tillmann
Published: (2026)

A Practical Algorithm with Performance Guarantees for the Art Gallery Problem
by: Hengeveld, Simon, et al.
Published: (2020)

Sometimes Two Irrational Guards are Needed
by: Meijer, Lucas, et al.
Published: (2022)

Devil's Games and $\text{Q}\mathbb{R}$: Continuous Games complete for the First-Order Theory of the Reals
by: Meijer, Lucas, et al.
Published: (2025)

On Classifying Continuous Constraint Satisfaction Problems
by: Miltzow, Tillmann, et al.
Published: (2021)

Representing Matroids over the Reals is $\exists \mathbb R$-complete
by: Kim, Eun Jung, et al.
Published: (2023)

Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain
by: de Berg, Sarita, et al.
Published: (2023)

The Existential Theory of the Reals as a Complexity Class: A Compendium
by: Schaefer, Marcus, et al.
Published: (2024)

Polyline Simplification has Cubic Complexity
by: Bringmann, Karl, et al.
Published: (2018)

Fréchet Distance in Unweighted Planar Graphs
by: van der Hoog, Ivor, et al.
Published: (2025)

Computing the Polytope Diameter is Even Harder than NP-hard (Already for Perfect Matchings)
by: Wulf, Lasse
Published: (2025)

The Point-Boundary Art Gallery Problem is $\exists\mathbb{R}$-hard
by: Stade, Jack
Published: (2022)

Drawings of Complete Multipartite Graphs Up to Triangle Flips
by: Aichholzer, Oswin, et al.
Published: (2023)

Online Hitting of Unit Balls and Hypercubes in $\mathbb{R}^d$ using Points from $\mathbb{Z}^d$
by: De, Minati, et al.
Published: (2023)

Online Geometric Hitting Set and Set Cover Beyond Unit Balls in $\mathbb{R}^2$
by: De, Minati, et al.
Published: (2023)

The Nesting Bird Box Problem is ER-complete: Sharp Hardness Results for the Hidden Set Problem
by: Meijer, Lucas, et al.
Published: (2026)

Shortest Paths in Geodesic Unit-Disk Graphs
by: Brewer, Bruce W., et al.
Published: (2026)

Minimum Selective Subset on Unit Disk Graphs and Circle Graphs
by: Manna, Bubai
Published: (2025)

Subcoloring of (Unit) Disk Graphs
by: Marin, Malory, et al.
Published: (2025)

On the existence of $L^p$-Optimal Transport maps for norms on $\mathbb{R}^N$
by: Liu, Guoxi, et al.
Published: (2024)

A Clique-Based Separator for Intersection Graphs of Geodesic Disks in $\mathbb{R}^2$
by: Aronov, Boris, et al.
Published: (2024)

Subexponential Algorithms for Clique Cover on Unit Disk and Unit Ball Graphs
by: Koana, Tomohiro, et al.
Published: (2024)

Unit-length Rectangular Drawings of Graphs
by: Alegria, Carlos, et al.
Published: (2022)

Constructive Polynomial Partitioning for Algebraic Curves in $\mathbb{R}^3$ with Applications
by: Aronov, Boris, et al.
Published: (2019)

Robust Algorithms for Finding Triangles and Computing the Girth in Unit Disk and Transmission Graphs
by: Klost, Katharina, et al.
Published: (2024)

Shortest Path Separators in Unit Disk Graphs
by: Harb, Elfarouk, et al.
Published: (2024)

Computing Maximum Cliques in Unit Disk Graphs
by: Tkachenko, Anastasiia, et al.
Published: (2025)

Improved Total Domination and Total Roman Domination in Unit Disk Graphs
by: Rout, Sasmita, et al.
Published: (2024)

Completeness in the Polynomial Hierarchy for many natural Problems in Bilevel and Robust Optimization
by: Grüne, Christoph, et al.
Published: (2023)

Computing the Girth of a Segment Intersection Graph
by: Chan, Timothy M., et al.
Published: (2026)

Oracle Separations for RPH
by: Hamm, Thekla, et al.
Published: (2025)

Dynamic Nearest-Neighbor Searching Under General Metrics in ${\mathbb R}^3$ and Its Applications
by: Agarwal, Pankaj K., et al.
Published: (2026)

Towards Crossing-Free Hamiltonian Cycles in Simple Drawings of Complete Graphs
by: Aichholzer, Oswin, et al.
Published: (2023)

The Presort Hierarchy for Geometric Problems
by: van der Hoog, Ivor, et al.
Published: (2026)

An Improved Algorithm for Shortest Paths in Weighted Unit-Disk Graphs
by: Brewer, Bruce W., et al.
Published: (2024)

ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs
by: An, Shinwoo, et al.
Published: (2024)

Query-Efficient Fixpoints of $\ell_p$-Contractions
by: Haslebacher, Sebastian, et al.
Published: (2025)