Oracle complexities for computional geometry of semi-algebraic sets and voronoi diagrams (Q753493)

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.