Planar 3-SAT → Plane oriented geometric spanner with bounded dilation Complexity open
Unsolved
Why this question matters
Moderate: the result would settle the hardness side of a natural directed geometric-network design problem relevant to sparse routing and motion-planning roadmaps. It would not resolve the separate undirected minimum-dilation triangulation question.
The 2025 journal version explicitly says hardness of minimum plane oriented spanners remains open. Its sparse-spanner hardness and Observation 4 about an FPTAS implication do not give the desired exact polynomial reduction.
The reduction to construct
An explicit planar Boolean 3-CNF instance, including its planar variable-clause incidence embedding, is given. Output YES if satisfiable and NO otherwise.
The input is a finite set of pairwise distinct rational-coordinate plane points and a positive rational threshold t, all in binary. The output is YES exactly when some simple strongly connected orientation of a plane straight-line graph on these points has oriented dilation at most t: for each point pair, the shortest directed closed walk through both has length at most t times the shortest triangle through them in the complete Euclidean graph. Otherwise output NO.
Construct deterministic polynomial-time maps F and G from Planar 3-SAT to this plane oriented-spanner decision problem, with exact YES/NO equivalence and polynomial bit bounds. A positive result establishes NP-hardness of minimum plane oriented dilation; it need not claim NP membership for arbitrary algebraic length comparisons.
High: NP-hardness for sparse oriented spanners permits nonplane edges, while the journal paper only sketches an approximate transfer from the undirected plane problem, itself open. A plausible route adapts its grid-Hamiltonian gadget with planar corridors; the missing lemma must force every low-dilation solution to use the intended local orientation without crossing.
What a complete answer must include
Specify rational point coordinates, threshold and geometric separation bounds, prove the planar orientation and dilation constraints in both directions, and account for exact arithmetic and output size. Later verification should evaluate small constructed instances independently.
References
Literature checked 2026-09-26. Checked the 2025 Algorithmica journal article, Definition 1, Section 3.1, Observation 4 and Conclusion; searched 2026-09-26 for 'plane oriented spanner NP-hard', 'oriented dilation triangulation hardness' and the newer SoCG 2025 oriented-spanner paper. No theorem settling the plane variant was located. Gates 1-4 pass; Gate 5 holds on an exact planar gadget; Gate 6 was not assessed.