Convex Hulls Under Uncertainty

Download

index.pdf

Date

2017-10-01

Author

Agarwal, Pankaj K.
Har-Peled, Sariel
Suri, Subhash
Yıldız, Hakan
Zhang, Wuzhou

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

132
views

30
downloads

We study the convex-hull problem in a probabilistic setting, motivated by the need to handle data uncertainty inherent in many applications, including sensor databases, location-based services and computer vision. In our framework, the uncertainty of each input point is described by a probability distribution over a finite number of possible locations including a null location to account for non-existence of the point. Our results include both exact and approximation algorithms for computing the probability of a query point lying inside the convex hull of the input, time-space tradeoffs for the membership queries, a connection between Tukey depth and membership queries, as well as a new notion of beta-hull that may be a useful representation of uncertain hulls.

URI

https://hdl.handle.net/11511/93930

Journal

ALGORITHMICA

DOI

https://doi.org/10.1007/s00453-016-0195-y

Collections

Department of Computer Engineering, Article

Suggestions

OpenMETU
Core

Convex Hulls under Uncertainty Agarwal, Pankaj K.; Har-Peled, Sariel; Suri, Subhash; Yıldız, Hakan; Zhang, Wuzhou (2014-01-01) We study the convex-hull problem in a probabilistic setting, motivated by the need to handle data uncertainty inherent in many applications, including sensor databases, location-based services and computer vision. In our framework, the uncertainty of each input point is described by a probability distribution over a finite number of possible locations including a null location to account for non-existence of the point. Our results include both exact and approximation algorithms for computing the probability...
On numerical optimization theory of infinite kernel learning Ozogur-Akyuz, S.; Weber, Gerhard Wilhelm (2010-10-01) In Machine Learning algorithms, one of the crucial issues is the representation of the data. As the given data source become heterogeneous and the data are large-scale, multiple kernel methods help to classify "nonlinear data". Nevertheless, the finite combinations of kernels are limited up to a finite choice. In order to overcome this discrepancy, a novel method of "infinite" kernel combinations is proposed with the help of infinite and semi-infinite programming regarding all elements in kernel space. Look...
Multi-Modal Learning With Generalizable Nonlinear Dimensionality Reduction KAYA, SEMİH; Vural, Elif (2019-08-26) In practical machine learning settings, there often exist relations or links between data from different modalities. The goal of multimodal learning algorithms is to efficiently use the information available in different modalities to solve multi-modal classification or retrieval problems. In this study, we propose a multi-modal supervised representation learning algorithm based on nonlinear dimensionality reduction. Nonlinear embeddings often yield more flexible representations compared to linear counterpa...
Domain adaptation on graphs by learning graph topologies: theoretical analysis and an algorithm Vural, Elif (The Scientific and Technological Research Council of Turkey, 2019-01-01) Traditional machine learning algorithms assume that the training and test data have the same distribution, while this assumption does not necessarily hold in real applications. Domain adaptation methods take into account the deviations in data distribution. In this work, we study the problem of domain adaptation on graphs. We consider a source graph and a target graph constructed with samples drawn from data manifolds. We study the problem of estimating the unknown class labels on the target graph using the...
Comparison of Cognitive Modeling and User Performance Analysis for Touch Screen Mobile Interface Design Ocak, Nihan; Çağıltay, Kürşat (Informa UK Limited, 2016-12-23) The aim of this study is to analyze and comparatively evaluate the usability of touch screen mobile applications through cognitive modeling and end-user usability testing methodologies. The study investigates the accuracy of the estimated results of a cognitive model produced for touch screen mobile phone interfaces. A mobile wallet application was chosen as the mobile software. The CogTool modeling tool was used as the cognitive modeling method. Eight tasks were determined and user tests were conducted in ...

Citation Formats

P. K. Agarwal, S. Har-Peled, S. Suri, H. Yıldız, and W. Zhang, “Convex Hulls Under Uncertainty,” ALGORITHMICA, vol. 79, no. 2, pp. 340–367, 2017, Accessed: 00, 2021. [Online]. Available: https://hdl.handle.net/11511/93930.