Networks · 1983 · 45 citations · 10 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsData StructuresComputational ComplexityGeometry ProcessingIntersection DetectionLine Segment IntersectionShortest Path AlgorithmsCombinatorial Complexity Of ArrangementsComplexity Of CrossingsIntersection CountingSegment Intersection Complexity AnalysisSegment-intersection Algorithms
Abstract Let S be a set of n horizontal and vertical segments on the plane, and let s, t ∈ S. A Manhattan path (of length k ) from s to t is an alternating sequence of horizontal and vertical segments s = r 0 , r 1 ,…, r k = t where r i intersects r i +1 , 0 ≤ i < k. An from all s ∈ S to t. Also given is a method to determine a maximum set of crossings (intersections of segments) with no two on the same segment, as well as a maximum set of nonintersecting segments, both in O ( n 3/2 log 2 log 2 n ) time. The latter algorithm is applied to decomposing, in O ( n 3/2 log 2 n ) time, a hole‐free union of n rectangles with sides parallel to the coordinate axes into the minimal number of disjoint rectangles. All the algorithms require O ( n log n ) space, and for all of them the factor log 2 n can be improved to log n log log n , at the cost of some complication of the basic data structure used.
10
Preserving order in a forest in less than logarithmic time
P. van Emde Boas · 1975 · 191 citations
On two-dimensional data organization I1
Elena Lodi, Fabrizio Luccio, Clio Mugnai et al. · Fundamenta Informaticae · 1979 · 72 citations