Halfplanar range search in linear space and \(O(n^{0.695})\) query time (Q1097038): Difference between revisions

From MaRDI portal
Created claim: Wikidata QID (P12): Q54309897, #quickstatements; #temporary_batch_1717956618549
ReferenceBot (talk | contribs)
Changed an Item
 
Property / cites work
 
Property / cites work: Multidimensional binary search trees used for associative searching / rank
 
Normal rank
Property / cites work
 
Property / cites work: Polygonal intersection searching / rank
 
Normal rank
Property / cites work
 
Property / cites work: Constructing Belts in Two-Dimensional Arrangements with Applications / rank
 
Normal rank
Property / cites work
 
Property / cites work: Quad trees: A data structure for retrieval by composite keys / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5585020 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4057549 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Partitioning with two lines in the plane / rank
 
Normal rank
Property / cites work
 
Property / cites work: Worst-case optimal insertion and deletion methods for decomposable searching problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Neighbor finding techniques for images represented by quadtrees / rank
 
Normal rank
Property / cites work
 
Property / cites work: Polygon Retrieval / rank
 
Normal rank

Latest revision as of 13:08, 18 June 2024

scientific article
Language Label Description Also known as
English
Halfplanar range search in linear space and \(O(n^{0.695})\) query time
scientific article

    Statements

    Halfplanar range search in linear space and \(O(n^{0.695})\) query time (English)
    0 references
    1986
    0 references
    Let S denote a set of n points in the Euclidean plane. A halfplanar range query asks for the number of points in S which are contained in a given halfplane h. The authors introduce a data structure which stores S in O(n) space allowing an \(O(n^{\log_ 2(1+\sqrt{5})-1})\) query-time implementation of the above problem. The structure which they call conjugation tree, but in more recent work is often referred to as ham- sandwich tree, can be built in O(n log n) time. This tree structure can be seen as an improvement of Willard's polygon tree. A line \(\ell\) is a bisector of S if it partitions S into two sets P and Q which both contain at most n/2 points. Line \(\ell\) is called a ham- sandwich cut of two sets P and Q if it bisects both of them. Such a cut always exists and the ham-sandwich tree T(S,\(\ell)\) can now be roughly defined as follows. The root stores \(\ell\) and the points in \(S\cap \ell\). Its two sons are the trees \(T(P,\ell_ 1)\) and \(T(Q,\ell_ 1)\), where \(\ell_ 1\) is the ham-sandwich cut of sets P and Q, the partition of S by \(\ell\). In splitting set S in four approximately equal parts within one ``level'', the ham-sandwich tree is, in a way, related to the well-known quad tree, although now, the separating lines are no longer necessarily axis-parallel. After the definition of the tree structure, the authors state their algorithm for the halfplanar range query and give the \(O(n^{0.695})\) worst-case time analysis. Then they shortly address how results of Megiddo can be used to construct the tree in O(n log n) time. They end their paper by noting that ham-sandwich trees may be made dynamic using generic methods of Overmars and van Leeuwen.
    0 references
    computational geometry
    0 references
    conjugation tree
    0 references
    ham-sandwich tree
    0 references
    halfplanar range query
    0 references
    worst-case time analysis
    0 references
    0 references
    0 references

    Identifiers