The convex hull of finitely generable subsets and its predicate transformer
File(s)LICS19_paper_186.pdf (164.41 KB)
Accepted version
Author(s)
Davari, Mohammad Javad
Edalat, Abbas
Lieutier, Andre
Type
Conference Paper
Abstract
We consider the domain of non-empty convex andcompact subsets of a finite dimensional Euclidean space torepresent partial or imprecise points in Computational Geom-etry. The convex hull map on such imprecise points is givendomain-theoretically by an inner and an outer convex hull. Weprovide a practical algorithm to compute the inner convex hullwhen there are a finite number of convex polytopes as partialpoints. A notion of pre-inner support function is introduced,whose convex hull gives the support function of the innerconvex hull in a general setting. We then show that the convexhull map is Scott continuous and can be extended to finitelygenerable subsets, represented by the Plotkin power domain ofthe underlying domain. This in particular allows us to computethe convex hull of attractors of iterated function systems infractal geometry. Finally, we derive a program logic for theconvex hull map in the sense of the weakest pre-condition fora given post-condition.
Date Issued
2020-08-05
Date Acceptance
2019-03-28
Citation
2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2020
Publisher
ACM/IEEE
Journal / Book Title
2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
Copyright Statement
© 2019 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Source
Thirty-Fourth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
Subjects
Science & Technology
Technology
Computer Science, Theory & Methods
Logic
Computer Science
Science & Technology - Other Topics
Domain Theory
Imprecision
Computability
Iterated Function Systems
POWER DOMAINS
ALGORITHM
ROBUSTNESS
FRACTALS
SYSTEMS
Publication Status
Published
Start Date
2019-06-24
Finish Date
2019-06-27
Coverage Spatial
Vancouver, Canada