dc.contributor.author | Cuong Nguyen | |
dc.date.accessioned | 2017-10-31T17:22:07Z | |
dc.date.available | 2017-10-31T17:22:07Z | |
dc.date.issued | 2017-10-31T17:22:07Z | |
dc.identifier.uri | http://hdl.handle.net/10222/73405 | |
dc.description.abstract | This thesis studies two well-known geometric structures in computational geometry: maximal points and convex hull. Extending the concepts to multiple maximal and convex layers is natural. We study the maximal and convex layers of a point set in $d$ dimensions drawn from a uniform or component-independent (CI) distribution. A distribution is component-independent if each coordinate of a point is chosen independently from a continuous distribution. Precisely, we want to compute and to bound the expected size of the first $k$ layers. For the first set of results, 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 two dimensions, 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. For the second set of results, we show that the $k$th 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))$. | en_US |
dc.language.iso | en | en_US |
dc.subject | maximal | en_US |
dc.subject | convex | en_US |
dc.subject | layers | en_US |
dc.subject | random point sets | en_US |
dc.subject | skyline | en_US |
dc.subject | computational geometry | en_US |
dc.subject | complexity | en_US |
dc.subject | component independent | en_US |
dc.title | MAXIMAL AND CONVEX LAYERS OF RANDOM POINT SETS | en_US |
dc.date.defence | 2017-10-26 | |
dc.contributor.department | Faculty of Computer Science | en_US |
dc.contributor.degree | Master of Computer Science | en_US |
dc.contributor.external-examiner | Dr. Qigang Gao | en_US |
dc.contributor.graduate-coordinator | Dr. Norbert Zeh | en_US |
dc.contributor.thesis-reader | Pr. Jeannette Janssen | en_US |
dc.contributor.thesis-reader | Dr. Alex Brodsky | en_US |
dc.contributor.thesis-supervisor | Dr. Norbert Zeh | en_US |
dc.contributor.thesis-supervisor | Dr. Meng He | en_US |
dc.contributor.ethics-approval | Not Applicable | en_US |
dc.contributor.manuscripts | Not Applicable | en_US |
dc.contributor.copyright-release | Not Applicable | en_US |