Unit Length Visibility Layers (UL VL)
Category: Logic
Input
A set of $n$ unit length, horizontal, nonintersecting line segments in the Euclidean plane, a designated segment $s$, and an integer $d$.
Problem
Is the label assigned to segment $s$ by the visibility layering process $d$?
Definitions
The visibility layering process is repeatedly to compute and delete the upper envelope of the remaining set of segments and label those segments with the current depth. The upper envelope consists of those segments visible from the point $(0, +\infty)$.
Status
Open (Atallah, Callahan, and Goodrich [1]).
Remarks
The problem is $\P$-complete if the restriction on unit lengths is removed [1]. See VL.