Linking disjoint segments into a simple polygon is hard

Abstract

Deciding whether a family of disjoint line segments in the plane can be linked into a simple polygon (or a simple polygonal chain) by adding segments between their endpoints is NP-hard.

Added a postscript and two more references

Cited by in corpus (1)

• Linking disjoint axis-parallel segments into a simple polygon is hard too