Geometric $(1+\varepsilon)$-Spanners with Few Crossings
For $n$ points in the plane and $\varepsilon>0$, we construct a $(1+\varepsilon)$-spanner with $O(n/\varepsilon)$ edges in which every edge has $\tilde{O}(1/\varepsilon^3)$ crossings, the total number of crossings is $\tilde{O}(n/\varepsilon^4)$, and the ratio between the lengths of any two crossing edges is $O(1/\varepsilon^2)$. Our spanner construction substantially improves on the previous upper bound for the number of crossings in a $(1+\varepsilon)$-spanner, and it is the first spanner construction that ensures $O(1)$ crossings per edge for any constant $\varepsilon>0$. In contrast, we…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.25040
curl -X POST /api/v1/records/arxiv/2607.25040/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.25040/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'