Treffer: Cache-Oblivious Red-Blue Line Segment Intersection

Title:
Cache-Oblivious Red-Blue Line Segment Intersection
Authors:
Arge, Lars, Mølhave, Thomas, Zeh, Norbert
Source:
Arge, L, Mølhave, T & Zeh, N 2008, 'Cache-Oblivious Red-Blue Line Segment Intersection', Lecture Notes in Computer Science, pp. 78-87. https://doi.org/10.1007/978-3-540-87744-8_8
Publication Year:
2008
Collection:
Aarhus University: Research
Subject Terms:
I/O-efficiency, external memory algorithms, cache-oblivious, algorithms, computational geometry
Document Type:
Fachzeitschrift article in journal/newspaper
Language:
English
DOI:
10.1007/978-3-540-87744-8_8
Availability:
https://pure.au.dk/portal/en/publications/7e3d9ed0-3246-11dd-9465-000ea68e967b
https://doi.org/10.1007/978-3-540-87744-8_8
Rights:
info:eu-repo/semantics/restrictedAccess
Accession Number:
edsbas.18605420
Database:
BASE

Weitere Informationen

We present an optimal cache-oblivious algorithm for finding all intersections between a set of non-intersecting red segments and a set of non-intersecting blue segments in the plane. Our algorithm uses $O(\frac{N}{B}\log_{M/B}\frac{N}{B}+T/B)$ memory transfers, where N is the total number of segments, M and B are the memory and block transfer sizes of any two consecutive levels of any multilevel memory hierarchy, and T is the number of intersections.