Pointed binary encompassing trees: Simple and optimal.
Michael M. Hoffmann, Csaba D. Tóth · 2005
Abstract. For n disjoint line segments in the plane we can construct a binary encompassing tree such that every vertex is pointed, what’s more, at every segment endpoint all incident edges lie in a halfplane defined by the incident input segment. Our algorithm runs in O(n log n) time which is known to be optimal in the algebraic computation tree model. Introduction. Interconnection graphs of disjoint line segments in the plane are fundamental structures in computational geometry, and often more complex objects are modelled by their boundary segments or polygons. One particularly well-studied example is