1
$\begingroup$

I am interested in the complexity of this problem:

Input: Given N points on integer 2D grid (N is even)

Question: Can we construct an orthogonal simple polygon from the set of N mid–points?

Each mid–point (an (x,y) pair with integer coordinates) is the midpoint of exactly one side; the polygon has N sides and its sides are all axis–parallel.

Does it become easier if no two mid–points share an x– or y–coordinate?

I know that the problem is NP-complete if each point is located at general position on a side excluding polygon's vertices.

Improve this question
$\endgroup$
2
  • $\begingroup$ You are given a set of N rocks placed on a two-dimensional integer grid. The task is to find an orthogonal closed simple path with N orthogonal line segments. You must collect each rock at the midpoint of a line segment. - Assume all line segments have even length. - Each rock lies at the midpoint of exactly one segment. - Each line segment has exactly one rock at its midpoint. - The angle between two successive line segments must be 90 or 270 degrees. Is there an efficient algorithm to solve it? Is it NP-complete? $\endgroup$ Commented Feb 12 at 5:20
  • $\begingroup$ Cross-posted to cstheory.stackexchange.com/questions/55136/… $\endgroup$ Commented Feb 22 at 6:59

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.