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.
Xu, Dianna
Keywords: Algorithms
Computational geometry
Convex hull
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)
ISBN: 978-1-5090-3568-7
ISSN: 1530-1834
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

CORE Recommender

Page view(s)

checked on Dec 26, 2022

Google ScholarTM



Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.