External memory planar point location with logarithmic updates (Q5920252): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
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
    0 references
    0 references
    0 references
    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
    0 references
    dynamic planar point location
    0 references
    external-memory model
    0 references

    Identifiers