Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems -- computations on discrete structures, geometrical problems and computations; G.2.1 [Discrete Mathematics]: Combinatorics -- combinatorical algorithms; I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling; I.3.7 [Computer Graphics]: Three-Dimensional Graphics and Realism -- visible line/surface algorithms
General Terms: Algorithms, Theory
Additional Key Words and Phrases: Computational complexity, computational geometry, hidden surface removal, randomized geometric algorithms, planar subdivision
Selected papers that cite this one
- Pankaj K. Agarwal, Mark de Berg, Ji\v{r}í Matou\v{s}ek, and Otfried Schwarzkopf. Constructing levels in arrangements and higher order Voronoi diagrams. SIAM Journal on Computing, 27(3):654-667, June 1998.
- Pankaj K. Agarwal, Ji\v{r}í Matou\v{s}ek, and Otfried Schwarzkopf. Computing many faces in arrangements of lines and segments. SIAM Journal on Computing, 27(2):491-505, March 1998.
- Bernard Chazelle. Computational geometry: A restrospective. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 75-94, Montréal, Québec, Canada, 23-25 May 1994.
- Ji\v{r}í Matou\v{s}ek. Derandomization in computational geometry. Journal of Algorithms, 20(3):545-580, May 1996.
Selected references
- Bernard Chazelle and Herbert Edelsbrunner. An optimal algorithm for intersecting line segments in the plane. In 29th Annual Symposium on Foundations of Computer Science, pages 590-600, White Plains, New York, 24-26 October 1988. IEEE.
- Richard J. Lipton and Robert Endre Tarjan. Application of a planar separator theorem. In 18th Annual Symposium on Foundations of Computer Science, pages 162-170, Providence, Rhode Island, 31 October-2 November 1977. IEEE.
- Ketan Mulmuley. A fast planar partition algorithm, I (extended abstract). In 29th Annual Symposium on Foundations of Computer Science, pages 580-589, White Plains, New York, 24-26 October 1988. IEEE.
- Ketan Mulmuley. On obstructions in relation to a fixed viewpoint. In 30th Annual Symposium on Foundations of Computer Science, pages 592-597, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.