Computing the Approximate Convex Hull in High Dimensions

Autor:	Sartipizadeh, Hossein, Vincent, Tyrone L.
Rok vydání:	2016
Předmět:	Computer Science - Computational Geometry Mathematics - Metric Geometry 52-xx
Druh dokumentu:	Working Paper
Popis:	In this paper, an effective method with time complexity of $\mathcal{O}(K^{3/2}N^2\log \frac{K}{\epsilon_0})$ is introduced to find an approximation of the convex hull for $N$ points in dimension $n$, where $K$ is close to the number of vertices of the approximation. Since the time complexity is independent of dimension, this method is highly suitable for the data in high dimensions. Utilizing a greedy approach, the proposed method attempts to find the best approximate convex hull for a given number of vertices. The approximate convex hull can be a helpful substitute for the exact convex hull for on-line processes and applications that have a favorable trade off between accuracy and parsimony. Comment: 5 pages, 1 figure, The more detailed version will be submitted
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1603.04422 Zobrazit plný text záznamu View this record from Arxiv