Show simple item record

dc.contributor.authorGuo, Yingda
dc.date.accessioned2017-09-01T18:18:33Z
dc.date.available2017-09-01T18:18:33Z
dc.identifier.urihttp://hdl.handle.net/10222/73284
dc.description.abstractWe propose the first data structure based on untangled monotonic chains for or- thogonal range searching in 3-dimensional space. The idea is an extension of the 2-dimensional chain partition algorithm proposed by Arroyuelo et al. (Untangled monotonic chains and adaptive range search, Theoretical Computer Science, 412(32), 2011). We also provide an improved algorithm for the chain untangling process, which in practice runs 25% percent faster than the untangling algorithm proposed in the experimental studies of Claude et al. (Range queries over untangled chains, SPIRE, Springer 2010). In the experimental evaluations, we first re-examined the experimen- tal studies conducted by Claude et al. for the 2-dimensional range searching algorithm based on untangled monotonic chains and found that the k-d tree implementation in CGAL, which is used as a reference for the experimental evaluation previously, is inefficient for the task at hand. Therefore, we implemented k-d trees ourselves and compared them against two range searching methods based on untangled chains. The experimental results showed that, in 2D, the performance of range searching methods based on untangled monotonic chains is similar to that of the k-d tree, which contra- dicts the experimental results of Claude et al. We then performed similar experimental studies in three dimensions. In 3D, the chain-decomposition-based range searching methods were unable to match the performance of k-d trees, which is mainly due to the difficulties in decomposing point sets into monotonic chains: our approaches either generated too many chains or used too much time to construct when the point set was large.en_US
dc.language.isoen_USen_US
dc.subject3D Range Searchingen_US
dc.subjectOrthogonal Range Searchingen_US
dc.title3D Range Searching Using Chain Decompositionen_US
dc.date.defence2017-08-18
dc.contributor.departmentFaculty of Computer Scienceen_US
dc.contributor.degreeMaster of Computer Scienceen_US
dc.contributor.external-examinern/aen_US
dc.contributor.graduate-coordinatorMalcolm Heywooden_US
dc.contributor.thesis-readerDirk Arnolden_US
dc.contributor.thesis-readerVlado Keseljen_US
dc.contributor.thesis-supervisorMeng Heen_US
dc.contributor.thesis-supervisorNorbert Zehen_US
dc.contributor.ethics-approvalNot Applicableen_US
dc.contributor.manuscriptsNot Applicableen_US
dc.contributor.copyright-releaseNot Applicableen_US
 Find Full text

Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record