A time-optimal solution to planar point location in ordered functional domains, with applications
Venkata Raman Bokka, Stephan Olariu, Jim L. Schwing, Linda F. Wilson, Albert Y. Zomaya · 2002
Consider a family C of continuous functions stored, in discretized form, one function per row in a mesh with multiple broadcasting of size /spl radic/n/spl times//spl radic/n. In a number of Computer Aided Geometric Design applications it is necessary to answer point location queries with respect to the given functions: e.g. cubic B-splines, control polygons of Bezier curves, etc. The main contribution of this work is to show that in such a domain an arbitrary collection of m, (1/spl les/m/spl les/n), point location queries can be answered in /spl Theta/(m//spl radic/n) time. We show that this is best possible on this platform. Our algorithms do not ignore the I/O time and see it as an important component of the overall processing time. In this regard, our algorithms feature a very attractive property, namely that the I/O time and the processing time are essentially the same.