Reporting intersections among thick objects |
| |
Authors: | Antoine Vigneron |
| |
Affiliation: | Department of Computer Science, The Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong |
| |
Abstract: | Let E be a set of n objects in fixed dimension d. We assume that each element of E has diameter smaller than D and has volume larger than V. We give a new divide and conquer algorithm that reports all the intersecting pairs in O(nlogn+(Dd/V)(n+k)) time and using O(n) space, where k is the number of intersecting pairs. It makes use of simple data structures and primitive operations, which explains why it performs very well in practice. Its restriction to unit balls in low dimensions is optimal in terms of time complexity, space complexity and algebraic degree. |
| |
Keywords: | Algorithms Computational geometry Divide and conquer Geometric intersection problems Robustness |
本文献已被 ScienceDirect 等数据库收录! |
|