External memory planar point location with logarithmic updates (Q5920252): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s00453-011-9541-2 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2119570197 / rank | |||
Normal rank |
Revision as of 23:46, 19 March 2024
scientific article; zbMATH DE number 6028473
Language | Label | Description | Also known as |
---|---|---|---|
English | External memory planar point location with logarithmic updates |
scientific article; zbMATH DE number 6028473 |
Statements
External memory planar point location with logarithmic updates (English)
0 references
26 April 2012
0 references
The authors of this paper describe a linear-space external-memory data structure for dynamic planar point location. In the external-memory model we have an internal memory that can hold \(M\) elements (edges or vertices), in which we can perform computations for free, and an unbounded external memory for storage; we can transfer a block of \(B \leq M / 2\) elements between internal and external memories at the cost of one input or output (I/O). The authors' data structure uses \(O (N / B)\) blocks to store a set of \(N\) line segments that divide the plane into faces, such that we can determine which face contains any given query point using \(O (\log_B^2 N)\) I/Os in the worst case, and insert or delete a line segment using \(O (\log_B N)\) amortized I/Os. The best previous solution was due to \textit{L. Arge} and \textit{J. Vahrenhold} [Comput. Geom. 29, No. 2, 147--162 (2004; Zbl 1056.68062)] and it also used \(O (N / B)\) blocks, \(O (\log_B^2 N)\) I/Os for queries in the worst case and \(O (\log_B N)\) amortized I/Os for deletion, but was more complicated and used \(O (\log_B^2 N)\) amortized I/Os for insertion.
0 references
dynamic planar point location
0 references
external-memory model
0 references