(in WR Franklin → Research)

This relies on the useful property that, if the input faces are IID (independently and identically distributed), then the expected number of visible edge pieces is linear in the number of input edges, and I can find them all in expected linear time.

This is remarkable since the total number of intersections of the projected input edges might be superlinear if the edges' lengths do not shrink fast enough. However, in that case, most of those intersections are hidden, and I can delete them in groups w/o spending even constant time per one. (1978)

1. . Wm Randolph Franklin and Mohan Kankanhalli. In Proceedings of SIGGRAPH'90, pages 87-94, Aug 1990. (paper).
2. . Wm Randolph Franklin, A linear time exact hidden surface algorithm. In Tutorial: Computer Graphics: Image Synthesis, pages 218-224. , 1988.
   Paper.
3. . Wm Randolph Franklin and Varol Akman. Computer Journal, 31(1):56-60, Feb 1988. (paper).
4. . Wm Randolph Franklin and Varol Akman. Computer Graphics Forum, 6(2):103-109, May 1987. (paper).
5. . Wm Randolph Franklin. Comput. Graph. Image Process., 15:364-379, 1981. (paper).
6. . Wm Randolph Franklin. Comput. Graph., 14(3):117-123, 1980. (paper).
7. . Wm Randolph Franklin. PhD thesis, Center for Research in Computing Technology, Harvard Univ., Jun 1978. (parts: 1, 2, 3, 4).

<< Connected Components Test Results Random | Research Page List | Nearpt3 >>