Range searching in a set of line segments
Mark H. Overmars · 1985
The range searching (or windowing) problem asks for an accommodation of a set of objects such that those objects that lie (partially) in a given axis-parallel rectangle can be reported efficiently. We solve the range searching problem for a set of n non-intersecting, but possibly touching, line segments in the plane and give a data structure that allows for range queries in Ο(k+ log2 n) time, where k is the number of reported answers. The structure is dynamic and allows for insertions and deletions of line segments in Ο(log2 n) time. The structure uses Ο(n log n) storage. The related problem of moving the window (range) parallel to one of the coordinate-axes, determining the first line segment that will become visible or stops being visible, is treated as well and similar bounds are obtained.