𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Convex hull problem with imprecise input and its solution

✍ Scribed by Takayuki Nagai; Seigo Yasutome; Nobuki Tokura


Publisher
John Wiley and Sons
Year
1999
Tongue
English
Weight
979 KB
Volume
30
Category
Article
ISSN
0882-1666

No coin nor oath required. For personal study only.

✦ Synopsis


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 assuming that the size of input error is given for each input point. For given n points, an external reliable region is calculated in On log n time, and an internal reliable region is calculated in On log n time (best case), or On 3 time (worst case).


πŸ“œ SIMILAR VOLUMES


Problem and its solution for actuator sa
✍ Maorui Zhang; Canghua Jiang πŸ“‚ Article πŸ“… 2008 πŸ› Elsevier Science 🌐 English βš– 601 KB

The modified Smith predictor (MSP) for integrating process with dead time (IPDT) has at least one pole at the origin of s-plane. The integral effect leads to large overshoot and slow settling time when the control signal exceeds the saturation limits of the system actuator. The windup problem in MSP