On obstructions in relation to a fixed viewpoint
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 592-597
- https://doi.org/10.1109/sfcs.1989.63540
Abstract
108 Efficient, randomized algorithms are given for the following problems: (1) construction of levels of order 1 to k in an arrangement of hyperplanes in any dimension; (2) construction of higher order Voronoi diagrams of order 1 to k in any dimension; (3) hidden surface removal for completely general scenes (intersecting and curved faces are allowed). A combinatorial tool in the form of a mathematical series called a theta series is associated with a configuration of polytopes in R/sup d/. It is used to study the combinatorial, as well as algorithmic, complexity of the geometric problems under consideration.Keywords
This publication has 9 references indexed in Scilit:
- On levels in arrangements and voronoi diagramsDiscrete & Computational Geometry, 1991
- An efficient algorithm for hidden surface removalACM SIGGRAPH Computer Graphics, 1989
- A fast planar partition algorithm, IIPublished by Association for Computing Machinery (ACM) ,1989
- Applications of random sampling in computational geometry, IIPublished by Association for Computing Machinery (ACM) ,1988
- Algorithms for diametral pairs and convex hulls that are optimal, randomized, and incrementalPublished by Association for Computing Machinery (ACM) ,1988
- An optimal algorithm for intersecting line segments in the planePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- A fast planar partition algorithm. IPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- On the lower envelope of bivariate functions and its applicationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- A Linear time algorithm for computing the Voronoi diagram of a convex polygonPublished by Association for Computing Machinery (ACM) ,1987