Please use this identifier to cite or link to this item:
|Title:||Convex Hull for Probabilistic Points||Authors:||Atalay, Fatma Betül
Friedler, Sorelle A.
|Issue Date:||2016||Publisher:||IEEE||Source:||Atalay, F. B., Friedler, S. A., & Xu, D. (2016, October). Convex Hull for Probabilistic Points. In 2016 29th SIBGRAPI Conference on Graphics, Patterns and Images (SIBGRAPI) (pp. 48-55). IEEE.||Abstract:||We analyze the correctness of an O(n log n) time divide-and-conquer algorithm for the convex hull problem when each input point is a location determined by a normal distribution. We show that the algorithm finds the convex hull of such probabilistic points to precision within some expected correctness determined by a user-given confidence value phi In order to precisely explain how correct the resulting structure is, we introduce a new certificate error model for calculating and understanding approximate geometric error based on the fundamental properties of a geometric structure. We show that this new error model implies correctness under a robust statistical error model, in which each point lies within the hull with probability at least phi, for the convex hull problem.||Description:||29th SIBGRAPI Conference on Graphics, Patterns and Images (2016 : Sao Paulo; Brazil)||URI:||https://ieeexplore.ieee.org/document/7813015
|Appears in Collections:||Bilgisayar Mühendisliği Bölümü / Department of Computer Engineering|
Scopus İndeksli Yayınlar Koleksiyonu / Scopus Indexed Publications Collection
WoS İndeksli Yayınlar Koleksiyonu / WoS Indexed Publications Collection
Show full item record
checked on Dec 26, 2022
Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.