Linear space data structures for two types of range search
Für den zwei- und den dreidimensionalen euklidischen Raum werden Aufgaben der ``Bereichssuche betrachtet: Seien eine Menge von n Punkten im Raum und eine Menge von Teilbereichen des Raumes gegeben (im \(E^ 2\) sind dies in dieser Arbeit alle Dreiecke, deren Seiten parallel zu drei gegebenen Richtungen sind - im \(E^ 3\) sind es die unendlich großen Oktanten, die sich von einem beliebigen Punkt aus parallel zu den Achsen jeweils ins negativ Unendliche erstrecken). Gefragt wird nach der Komplexität der Algorithmen, welche alle Punkte der gegebenen Mengen ermitteln, die in einem der Teilbereiche liegen. Als neues Resultat können die Autoren angeben: Der benötigte Speicherplatz hat lineare Komplexität O(n) und die Bearbeitungszeit für eine Anfrage im \(E^ 2\) bzw. im \(E^ 3\) verhält sich wie \(O(k+\log n)\) resp. \(O(k+\log^ 2n)\), wobei k die Anzahl der gefundenen Punkte ist. Erreichbar wurde dies durch einen aufwendigeren Vorprozeß, welcher die gegebenen n Punkte in einer baumartigen Datenstruktur ``vorsortiert und der sich bei vielen Anfragen gewissermaßen amortisiert.
- Applications of a Planar Separator Theorem
- Filtering Search: A New Approach to Query-Answering
- Finding the intersection of two convex polyhedra
- Fractional cascading. I: A data structuring technique
- Halfplanar range search in linear space and \(O(n^{0.695})\) query time
- Multidimensional divide-and-conquer
- On Finding the Maxima of a Set of Vectors
- Optimal Point Location in a Monotone Subdivision
- Optimal Search in Planar Subdivisions
- Optimal solutions for a class of point retrieval problems
- Polygon Retrieval
- Primitives for the manipulation of general subdivisions and the computation of Voronoi
- Priority Search Trees
- The power of geometric duality
- Fractional cascading. II: Applications
- Algorithms for three-dimensional dominance searching in linear space.
- Features of solving the range searching problems for d-dimensional case
- On Dominance Reporting in 3D
- An efficient algorithm for the 1D total visibility-index problem and its parallelization
- An application of m-ary trees to the design of data structures for geometric searching problems
- Space Efficient Multi-dimensional Range Reporting
- Linear space adaptive data structures for planar range reporting
- Incremental hive graph
- Point enclosure problem for homothetic polygons
- Dominance for enclosure problems
- Path and ancestor queries over trees with multidimensional weight vectors
- On space efficient two dimensional range minimum data structures
- Dominance for enclosure problems
- Point enclosure problem for homothetic polygons
- Counting permutation patterns with multidimensional trees
- The intersection searching problem for c-oriented polygons
This page was built for publication: Linear space data structures for two types of range search
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q578916)
