Open Access System for Information Sharing

Login Library

 

Article
Cited 0 time in webofscience Cited 0 time in scopus
Metadata Downloads

Finding pairwise intersections of rectangles in a query rectangle

Title
Finding pairwise intersections of rectangles in a query rectangle
Authors
Oh, E.Ahn, H.-K.
Date Issued
Dec-2019
Publisher
ELSEVIER
Abstract
We consider the following problem: Preprocess a set S of n axis-parallel boxes in R-d so that given a query with an axis-parallel box in R-d, the pairs of boxes of S whose intersection intersects the query box can be reported efficiently. For the case that d = 2, we present a data structure of size O(n logn) supporting O(logn + k) query time, where k is the size of the output. This improves the previously best known result by de Berg et al. which requires O(logn + k logn) query time using O(n logn) space. There has been no result known for this problem for higher dimensions, except that for d = 3, the best known data structure supports O(root n log(2)n + k log(2)n) query time using O(n root nlogn) space. For a fixed dimension d > 2, we present a data structure supporting O(n(1-delta)log(d-1) n +k log(d-1) n) query time for any constant 0 < delta < 1. The size of the data structure is O(n(delta d-28+1)logn). (C) 2019 Elsevier B.V. All rights reserved.
URI
http://oasis.postech.ac.kr/handle/2014.oak/101215
ISSN
0925-7721
Article Type
Article
Citation
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, vol. 85, 2019-12
Files in This Item:
There are no files associated with this item.

qr_code

  • mendeley

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Related Researcher

Researcher

안희갑AHN, HEE KAP
Grad. School of AI
Read more

Views & Downloads

Browse