Non robustness and imprecise inputs leads to unstable and inconsistent results in computations. We studied a theoretical model which uses domains as representation structure and ensures robustness and computability in geometric objects and algorithms. I will talk about our recent results on this model and particularly about convex hull problem.
We consider the domain of non-empty convex and compact subsets of a finite dimensional Euclidean space to represent partial or imprecise points in computational geometry. The convex hull map on such imprecise points is given domain-theoretically by an inner and an outer convex hull. We show that the convex hull map is Scott continuous and can be extended to finitely generable subsets, represented by the Plotkin power domain of the underlying domain. This in particular allows us to compute, for the first time, the convex hull of attractors of iterated function systems in fractal geometry. We derive a program logic for the convex hull map in the sense of the weakest pre-condition for a given post-condition and show that the convex hull predicate transformer is computable.
This talk is based on a paper which presented in LICS 2019.