Aarhus University Seal / Aarhus Universitets segl

Lars Arge

Cache-Oblivious Red-Blue Line Segment Intersection

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearchpeer-review

  • Lars Arge
  • Thomas Mølhave, Denmark
  • Norbert Zeh, Dalhousie University, Canada
  • Department of Computer Science
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.
Original languageEnglish
Book seriesLecture Notes in Computer Science
Pages (from-to)78-87
Number of pages10
ISSN0302-9743
DOIs
Publication statusPublished - 2008
Event16th Annual European Symposium on Algorithms - Karlsruhe, Germany
Duration: 15 Sep 200817 Sep 2008
Conference number: 16

Conference

Conference16th Annual European Symposium on Algorithms
Number16
CountryGermany
CityKarlsruhe
Period15/09/200817/09/2008

    Research areas

  • I/O-efficiency, external memory algorithms, cache-oblivious, algorithms, computational geometry

See relations at Aarhus University Citationformats

ID: 11529977