Convex hull problem with imprecise input and its solution

In realistic case, input coordinates are subject to input errors and output is affected by input errors. But in many geometric algorithms output is calculated under the assumption that all input is accurate, so the output does not reflect the effect of input errors. Such an output is meaningless because, for example, in the convex hull problem the shape of the output polygon may closely resemble the true polygon or may be very different from the true polygon. We can not derive any certain result or conclusion from such an output. Under the existence of input errors, we should calculate output which reflects input errors. In this paper, we consider a convex hull problem in a situation that all input coordinates contain some errors. We regard this problem as to compute an internal reliable region which is always included in all possible hulls and an external reliable region which always contains all possible hulls. We show that external reliable region can be constructed in O(n log n) time (n is the number of input points), and internal reliable region can be constructed in O(n log n) time (best case), O(n³) time (worst case).