Oracle complexities for computional geometry of semi-algebraic sets and voronoi diagrams (Q753493)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Oracle complexities for computional geometry of semi-algebraic sets and voronoi diagrams |
scientific article |
Statements
Oracle complexities for computional geometry of semi-algebraic sets and voronoi diagrams (English)
0 references
1990
0 references
In the computational geometry literature many algorithms are described in a high-level way, in that certain elementary operations like e.g. computing the (first) point of intersection of two curves, are assumed to be available at constant cost. While this point of view is acceptable in linear geometry it is incomplete if objects of higher algebraic degree must be processed. This problem is addressed in the present paper. The authors provide a useful survey on the complexity of oracle operations that occur in computing convex hulls and Voronoi diagrams of higher degree objects.
0 references
computational geometry
0 references
oracle complexity
0 references
convex hulls
0 references
Voronoi diagrams
0 references