Euclidea is APX-hard: Complexity of Optimizing Euclidean Constructions
We prove that it is APX-hard to find the shortest straightedge-and-compass construction of a given geometric object, under either measure of “moves” in the puzzle video game Euclidea. In particular, the problem is NP-hard, even to approximate within a factor of √2 (or a factor of 2 under the Unique Games Conjecture).
Authors
- Victor Luo
- Erik D. Demaine (ORCID: https://orcid.org/0000-0003-3803-5703)
Publication Details
- Journal
- Journal of Information Processing
- Published
- 2025-01-01
- DOI
- https://doi.org/10.2197/ipsjjip.33.1110
- Primary Topic
- Computational Geometry and Mesh Generation
- Type
- article
- Field-Weighted Citation Impact
- 0.00