Computational geometry column 9
Joseph O’Rourke · ACM SIGACT News · 1990
bitnet 1 Old ProblemsOutput-sensitive Hidden Surface Removal .Advances continue to be made on this difficul t and important problem .The latest is an algorithm by Overmars and Sharir that attain s true output-sensitive behavior at the expense of restricting the input [OS89] .Specifically, if the input polygons are given with a proper depth-priority ordering, then their algorith m has complexity O(nvlog n) time, where k is the number of vertices in the output scene .Not all sets of polygons can be consistently ordered ; many practical algorithms partition th e polygons into pieces until such an ordering is possible .Nevertheless the class of orderable sets of polygons is an important one .They conjecture that their approach might achiev e O(n 2/3 k2/3 ) .Prison Yard Problem .Kleitman and Fiiredi have settled the conjecture that In/21 guards suffice to simultaneously see every point in both the interior and exterior of a simple polygon o f n vertices [K1e90] [O'R87] !Acyclic Triangulations .Aurenhammer has shown that there exist acyclic triangulations tha t are not realizable as the projection of the lower faces of a 3-polytope [O'R89] [Ede89] .