Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.11851/1989
Title: Convex Hull for Probabilistic Points
Authors: Atalay, Fatma Betül
Friedler, Sorelle A.
Xu, Dianna
Keywords: Algorithms
Computational geometry
Convex hull
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
https://arxiv.org/pdf/1412.1039.pdf
https://hdl.handle.net/20.500.11851/1989
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)

4
checked on Mar 25, 2024

Google ScholarTM

Check




Altmetric


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