A dynamic data structure for efficient bounded line range search
| dc.contributor.author | Le, Thuy, T. | |
| dc.contributor.author | Nickerson, Bradford, G. | |
| dc.date.accessioned | 2023-03-01T18:27:02Z | |
| dc.date.available | 2023-03-01T18:27:02Z | |
| dc.date.issued | 2010 | |
| dc.description.abstract | A dynamic data structure for efficient axis-aligned orthogonal range search on a set of n lines in a bounded plane is presented. The algorithm requires O(log n + k) time in the worst case to find all lines intersecting an axis aligned query rectangle R, for k the number of lines in range. O(n + lambda) space is required for the data structure used by the algorithm, where lambda is the number of intersection points among the lines. Insertion of a new rightmost line l or deletion of a leftmost line l requires O(n) time in the worst case. For a sparse arrangement of lines (i.e., for lambda = O(n)), insertion of a rightmost line l or deletion of a leftmost line l requires O (√n) expected time. | |
| dc.description.copyright | Copyright @ Thuy T. T. Le and Bradford G. Nickerson, 2010. | |
| dc.identifier.uri | https://unbscholar.lib.unb.ca/handle/1882/14682 | |
| dc.rights | http://purl.org/coar/access_right/c_abf2 | |
| dc.subject.discipline | Computer Science | |
| dc.title | A dynamic data structure for efficient bounded line range search | |
| dc.type | technical report |
Files
Original bundle
1 - 1 of 1