Showing cs.CGShow all
3 papers · 1 filter
cs.CG2024
Computational Complexities of Folding
David Eppstein
We prove several hardness results on folding origami crease patterns. Flat-folding finite crease patterns is fixed-parameter tractable in the ply of the folded pattern (how many la…
cs.CG2024
Noncrossing Longest Paths and Cycles
Greg Aloupis, Ahmad Biniaz, Prosenjit Bose +7
Edge crossings in geometric graphs are sometimes undesirable as they could lead to unwanted situations such as collisions in motion planning and inconsistency in VLSI layout. Short…
cs.CG2024
Maintaining Light Spanners via Minimal Updates
Hadi Khodabandeh, David Eppstein
We study the problem of maintaining a lightweight bounded-degree -spanner of a dynamic point set in a -dimensional Euclidean space, where and $d…