Hidden-line removal

A face of a polyhedron is a planar polygon bounded by straight line segments, called edges.

Therefore, a computational-complexity approach expressing resource requirements (such as time and memory) as the function of problem sizes is crucial.

Any hidden-line algorithm has to determine the union of Θ(n) hidden intervals on n edges in the worst case.

However, the log n factor was eliminated by Devai,[4] who raised the open problem whether the same optimal O(n2) upper bound existed for hidden-surface removal.

The other open problem, raised by Devai,[4] of whether there exists an O(n log n + v)-time hidden-line algorithm, where v, as noted above, is the number of visible segments, is still unsolved at the time of writing.

As the product of the processor number and the running time is asymptotically greater than Θ(n2), the sequential complexity of the problem, the algorithm is not work-optimal, but it demonstrates that the hidden-line problem is in the complexity class NC, i.e., it can be solved in polylogarithmic time by using a polynomial number of processors.

Reif and Sen [17] proposed an O(log4 n)-time algorithm for the hidden-surface problem, using O((n + v)/log n) CREW PRAM processors for a restricted model of polyhedral terrains, where v is the output size.

Cook, Dwork and Reischuk gave an Ω(log n) lower bound for finding the maximum of n integers allowing infinitely many processors of any PRAM without simultaneous writes.