6
$\begingroup$

This is a variant of two as-yet unsolved MO questions cited below. Let $P$ be a closed polyhedron in $\mathbb{R}^3$. The task is to find a shortest path $\sigma$ on the surface of $P$ from which all the surface may be "inspected," which is interpreted as requiring that $\sigma$ touch every face of $P$. The path $\sigma$ might only touch a corner or edge of a face, but that suffices to inspect the face. For example, these seem straightforward:


      Inspect123
          Optimal inspection paths on the tetrahedron, cube, octahedron.
I am less certain of the icosahedron. Update: Gerhard Paseman's $5$-edge path is shorter.
          InspectIcosa
          Left path length: $2+\sqrt{13} \approx 5.6$. Right: $5$.
I believe it is not difficult to show the problem is NP-hard (by reduction from TSP), so approximations are likely necessary. I have a sense, perhaps a vague memory, that this has been investigated in the literature, maybe only for restricted sets of convex polyhedra (e.g., the Platonic & Archimedean solids). But I have not been able to find any citations. If anyone can find a reference, or make a useful observation, it would be appreciated.


"Optimal inspection path on a sphere"
"Shortest closed curve to inspect a sphere"

$\endgroup$
  • 1
    $\begingroup$ Happy New Year! $\endgroup$ – Joseph O'Rourke Dec 31 '15 at 20:45
  • 2
    $\begingroup$ Likewise. I get 5 for the icosahedron by following edges. Gerhard "And Happy Valentine's Day Too" Paseman, 2015.12.31. $\endgroup$ – Gerhard Paseman Dec 31 '15 at 21:05
  • $\begingroup$ @GerhardPaseman: Ah, yes, I see the $5$-edge path. Thanks! $\endgroup$ – Joseph O'Rourke Dec 31 '15 at 21:27
  • $\begingroup$ The problem for the curved surface (inspecting the sphere) does not seem to the limiting case of the polyhedral version. Do you have a link in mind ? $\endgroup$ – ARi Jan 1 '16 at 13:22
  • 1
    $\begingroup$ Someone has taken out a patent on a "polyhedron inspection apparatus", google.com/patents/US6892593 (but don't bother going there, it has nothing to do with the question). $\endgroup$ – Gerry Myerson Jan 1 '16 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.