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, -levels, or the set of cells containing a given set of points. The problem of finding the arrangement vertex with the median -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. Non-Euclidean line arrangements A pseudoline arrangement is a family of curves that share similar topological properties with a line arrangement. These can be defined most simply in the projective plane as simple closed curves any two of which meet in a single crossing point. A pseudoline arrangement is said to be stretchable if it is combinatorially equivalent to a line arrangement. Determining stretchability is a difficult computational task: it is complete for the existential theory of the reals to distinguish stretchable arrangements from non-stretchable ones. Every arrangement of finitely many pseudolines can be extended so that they become lines in a "spread", a type of non-Euclidean incidence geometry in which every two points of a topological plane are connected by a unique line (as in the Euclidean plane) but in which other axioms of Euclidean geometry may not apply. Another type of non-Euclidean geometry is the hyperbolic plane, and arrangements of hyperbolic lines in this geometry have also been studied. Any finite set of lines in the Euclidean plane has a combinatorially equivalent arrangement in the hyperbolic plane (e.g. by enclosing the vertices of the arrangement by a large circle and interpreting the interior of the circle as a Klein model of the hyperbolic