Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
Maximal and Convex Layers of Random Point Sets
verfasst von : Meng He, Cuong P. Nguyen, Norbert Zeh
Erschienen in: LATIN 2018: Theoretical Informatics
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
We study two problems concerning the maximal and convex layers of a point set in d dimensions. The first is the average-case complexity of computing the first k layers of a point set drawn from a uniform or component-independent (CI) distribution. We show that, for \(d \in \{2,3\}\), the first \(n^{1/d-\epsilon }\) maximal layers can be computed using \(dn + o(n)\) scalar comparisons with high probability. For \(d \ge 4\), the first \(n^{1/2d-\epsilon }\) maximal layers can be computed within this bound with high probability. The first \(n^{1/d-\epsilon }\) convex layers in 2D, the first \(n^{1/2d-\epsilon }\) convex layers in 3D, and the first \(n^{1/(d^2+2)}\) convex layers in \(d \ge 4\) dimensions can be computed using \(2dn + o(n)\) scalar comparisons with high probability. Since the expected number of maximal layers in 2D is \(2\sqrt{n}\), our result for 2D maximal layers shows that it takes \(dn + o(n)\) scalar comparisons to compute a \(1/n^\epsilon \)-fraction of all layers in the average case. The second problem is bounding the expected size of the kth maximal and convex layer. We show that the kth maximal and convex layer of a point set drawn from a continuous CI distribution in d dimensions has expected size \(O(k^d \log ^{d-1} (n/k^d))\).