Editing Hidden-line removal (section)

== Parallel algorithms ==
In 1988 Devai proposed<ref>F. Devai. An ''O''(log ''N'') parallel time exact hidden-line algorithm. ''Advances in Computer Graphics Hardware II'', pp. 65–73, 1988.</ref> an ''O''(log ''n'')-time parallel algorithm using ''n''<sup>2</sup> processors for the hidden-line problem under the [[concurrent read, exclusive write]] (CREW) parallel random-access machine (PRAM) model of computation.  As the product of the processor number and the running time is asymptotically greater than Θ(''n''<sup>2</sup>), the sequential complexity of the problem, the algorithm is not work-optimal, but it demonstrates that the hidden-line problem is in the [[NC (complexity)|complexity class NC]], i.e., it can be solved in polylogarithmic time by using a polynomial number of processors.

Hidden-surface algorithms can be used for hidden-line removal, but not the other way around. Reif and Sen <ref>J. H. Reif and S. Sen. [http://repository.ias.ac.in/90070/1/4-Pub.pdf An efficient output-sensitive hidden surface removal algorithm and its parallelization]. In ''Proc. 4th Annual Symp. on Computational Geometry'', SCG ’88, pp. 193–200, New York, NY, USA, 1988.</ref> proposed an ''O''(log<sup>4</sup> ''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.

In 2011 Devai published<ref name=Devai11>F. Devai. [https://www.researchgate.net/profile/Frank_Devai2/publication/225694183_An_Optimal_Hidden-Surface_Algorithm_and_Its_Parallelization/links/5595457608ae99aa62c6869c.pdf An optimal hidden-surface algorithm and its parallelization]. In ''Computational Science and Its Applications'', ICCSA 2011, volume 6784 of ''Lecture Notes in Computer Science'', pp 17–29. Springer Berlin/Heidelberg, 2011.</ref> an ''O''(log ''n'')-time hidden-surface, and a simpler, also ''O''(log ''n'')-time, hidden-line algorithm. The hidden-surface algorithm, using ''n''<sup>2</sup>/log ''n'' CREW PRAM processors, is work-optimal.

The hidden-line algorithm uses ''n''<sup>2</sup> exclusive read, exclusive write (EREW) PRAM processors.  The EREW model is the PRAM variant closest to real machines.  The hidden-line algorithm does ''O''(''n''<sup>2</sup> log ''n'') work, which is the upper bound for the best sequential algorithms used in practice.

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.<ref>S. Cook, C. Dwork, and R. Reischuk. [https://epubs.siam.org/doi/abs/10.1137/0215006 Upper and lower time bounds for parallel random access machines without simultaneous writes]. ''SIAM J. Comput''., 15:87–97, February 1986.</ref>  Finding the maximum of ''n'' integers is constant-time reducible to the hidden-line problem by using ''n'' processors.  Therefore, the hidden-line algorithm is time optimal.<ref name=Devai11 />