A new approach to rectangle intersections

DOI10.1080/00207168308803365zbMath0513.68059OpenAlexW1593675831MaRDI QIDQ3659159

Herbert Edelsbrunner

Publication date: 1983

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207168308803365

zbMATH Keywords

computational geometrysearchingdata structureconcrete complexityrectilinearly-oriented rectangle

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Data structures (68P05) Information storage and retrieval of data (68P20) Discrete mathematics in relation to computer science (68R99)

Related Items

A practical divide-and-conquer algorithm for the rectangle intersection problem ⋮ Computing on a free tree via complexity-preserving mappings ⋮ A UNIFIED APPROACH TO AUTOMATIC LABEL PLACEMENT ⋮ Scanline algorithms on a grid ⋮ Algorithms for the multiple label placement problem ⋮ A space-optimal solution of general region location ⋮ Unnamed Item ⋮ Internal and external algorithms for the point-in-regions problem - the INSIDE join of georelational algebra ⋮ Reporting intersections among thick objects.

Cites Work

• A Lower Bound on the Complexity of Orthogonal Range Queries
• Counting and Reporting Intersections of d-Ranges