In computational geometry, many implementing issues have been studied which arise from arithmetic error or input error. For the convex hull problem, a basic problem in this field, many algorithms have been studied concerning these issues. However, most of them consider arithmetic error. There are few studies on the convex hull problem in a situation where input error exists. In this paper, we consider the convex hull problem with the existence of input error and introduce a method where the output hull is divided into two parts: one sensitive to input error and the other insensitive to it. As the insensitive part, the boundaries of regions which are always inside or outside of all possible hulls are constructed. A region which is always inside of all possible hulls is called an internal reliable region, and a region which is always outside of them is called an external reliable region. We show algorithms which calculate an internal reliable region and an external reliable region as suming that the size of input error is given for each input point. For given n points, an external reliable region is calculated in O(n log n)time. and an internal reliable region is calculated in O(n log n)time (best case), or O(n3) time (worst case).
展开▼
