← All Problems
Open

2-Oriented Weighted Planar Partitioning (2OWPP)

Category: Logic

Input

A set of nonintersecting segments $s_1, \ldots, s_n$ in the Euclidean plane, a set of associated integer weights $w_1, \ldots, w_n$, and two designated segments $r$ and $t$. The segments are 2-oriented meaning that there are only two different possible slopes for the segments.

Problem

Do segments $r$ and $t$ “touch” in the partitioning of the plane constructed by extending segments in the order of their weights? Segments are extended until they reach another segment or a previous segment extension.

Status

Open (Atallah, Callahan, and Goodrich [1]).

Remarks

The 3-oriented version, 3OWPP, in which three different slopes are allowed, is $\P$-complete [1].

References

  1. M. J. Atallah, P. Callahan, and M. T. Goodrich (1990). P-complete geometric problems.
  2. Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press. Problem B.6.3.

Related Problems