minimum perimeter convex hull of imprecise points in convex regions
Imprecise points are points in R 2 whose exact location is unknown. For each point, we only know it is contained in a region of R 2 , which is called the uncertainty region of the point. The research we present in this video focuses on the problem of finding the minimum perimeter convex hull of a set of imprecise points, where each uncertainty region is closed, convex, and the regions may intersect. We first present and animate our theoretical findings: as each point moves inside its uncertainty region, the perimeter of the resulting convex hull is a convex function on the position of the points; as a consequence, any local minimum of the perimeter is a global minimum. We then show the possible positions of imprecise points inside their uncertainty region. Finally, we demonstrate an algorithm for finding the minimum perimeter convex hull of a set of imprecise points.
minimum perimeter convex hull uncertainty region