Introduction

For the given task, the following data are specified: a list of bounding-boxes of 2D geometrical objects and a tested object (point, line segment, rectangle, etc.) as an input. The output is a list of bounding boxes which have an intersection with the tested object. Searching within bounding-boxes takes O(n) complexity. Instead of it we will build a kind of hierarchy (tree). Then we will traverse this hierarchy. The basic idea is to take two bounding-boxes and group them together, it means to create one bigger bounding-box around them. This can be represented as one node of a tree. The whole thing is about what kind of a tree is the best and how to create it simply.

The paper is organized as follows: Chapter 2 contains presumptions, Chapter 3 describes our solution, Chapter 4 discuss complexity, Chapter 5 presents results of measurements and the last Chapter contains summary.