Arrangement of Lines - Algorithms

Algorithms

Constructing an arrangement means, given as input a list of the lines in the arrangement, computing a representation of the vertices, edges, and cells of the arrangement together with the adjacencies between these objects, for instance as a doubly connected edge list. Due to the zone theorem, arrangements can be constructed efficiently by an incremental algorithm that adds one line at a time to the arrangement of the previously added lines: each new line can be added in time proportional to its zone, resulting in a total construction time of O(n2). However, the memory requirements of this algorithm are high, so it may be more convenient to report all features of an arrangement by an algorithm that does not keep the entire arrangement in memory at once. This may again be done efficiently, in time O(n2) and space O(n), by an algorithmic technique known as topological sweeping. Computing a line arrangement exactly requires a numerical precision several times greater than that of the input coordinates: if a line is specified by two points on it, the coordinates of the arrangement vertices may need four times as much precision as these input points. Therefore, computational geometers have also studied algorithms for constructing arrangements efficiently with limited numerical precision.

As well, researchers have studied efficient algorithms for constructing smaller portions of an arrangement, such as zones, k-levels, or the set of cells containing a given set of points. The problem of finding the arrangement vertex with the median x-coordinate arises (in a dual form) in robust statistics as the problem of computing the Theil–Sen estimator of a set of points.

Marc van Kreveld suggested the algorithmic problem of computing shortest paths between vertices in a line arrangement, where the paths are restricted to follow the edges of the arrangement, more quickly than the quadratic time that it would take to apply a shortest path algorithm to the whole arrangement graph. An approximation algorithm is known, and the problem may be solved efficiently for lines that fall into a small number of parallel families (as is typical for urban street grids), but the general problem remains open.