On the complexity of convex hull algorithms if rotational minima can be found very fast

For a large class of time functionsT, we show the following: Assuming that there is some parallel processor which requiresθ(T(j)) time units when searching the minimum amongj arbitrary points with respect to an arbitrary rotational ordering. Then the planar Convex Hull Problem forn points is of the complexityθ(nT(n)). Also our auxiliar results are significant: We shall deal with a graph theoretical lemma, and we shall prove a result which is similar to those of [Frie 72] and [Schm 83]: The worst-case complexity of the sorting problem is Ω(n log (n)) even if the operations “+”, “-”, “×”, “/” and queries ‘p(x) ∈ A?’ are possible where the rational functionp and the setA ?IR are arbitrary. At last, we describe the architecture of a network which actually searches polar minima inθ(T(j)) time units.