Aarhus University Seal / Aarhus Universitets segl

Lars Arge

An optimal dynamic interval stabbing-max data structure?

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Pankaj Kumar Agarwal, United States
  • Lars Arge
  • Ke Yi, Hong Kong
  • Department of Computer Science
In this paper we consider the dynamic stabbing-max problem, that is, the problem of dynamically maintaining a set S of n axis-parallel hyper-rectangles in Rd, where each rectangle sS has a weight w(s) ∈ R, so that the rectangle with the maximum weight containing a query point can be determined efficiently. We develop a linear-size structure for the one-dimensional version of the problem, the interval stabbing-max problem, that answers queries in worst-case O(log n) time and supports updates in amortized O(log n) time. Our structure works in the pointer-machine model of computation and utilizes many ingredients from recently developed external memory structures. Using standard techniques, our one-dimensional structure can be extended to higher dimensions, while paying a logarithmic factor in space, update time, and query time per dimension. Furthermore, our structure can easily be adapted to external memory, where we obtain a linear-size structure that answers queries and supports updates in O(logB n) I/Os, where B is the disk block size.
Original languageEnglish
Title of host publicationProceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms
Number of pages9
PublisherSociety for Industrial and Applied Mathematics
Publication year2005
Pages803-812
ISBN (print)0-89871-585-7
Publication statusPublished - 2005
EventACM-SIAM Symposium on Discrete Algorithms - Vancouver, Canada
Duration: 23 Jan 200527 May 2005
Conference number: 16

Conference

ConferenceACM-SIAM Symposium on Discrete Algorithms
Nummer16
LandCanada
ByVancouver
Periode23/01/200527/05/2005

See relations at Aarhus University Citationformats

ID: 10650521