# Pointed binary encompassing trees

M. Hoffmann, B. Speckmann, Cs.D. Tóth

4 Citaten (Scopus)

## Samenvatting

We show that for any set of disjoint line segments in the plane there exists a pointed binary encompassing tree T, that is, a spanning tree on the segment endpoints that contains all input segments, has maximum degree three, and every vertex v $\in$ T is pointed, that is, v has an incident angle greater than $\pi$. Such a tree can be completed to a minimum pseudo-triangulation. In particular, it follows that every set of disjoint line segments has a minimum pseudo-triangulation of bounded vertex degree.
Originele taal-2 Engels Algorithm Theory - SWAT 2004 (Proceedings 9th Scandinavian Workshop on Algorithm Theory, Humlebaek, Denmark, July 8-10, 2004) T. Hagerup, J. Katajainen Berlin Springer 442-454 3-540-22339-8 https://doi.org/10.1007/978-3-540-27810-8_38 Gepubliceerd - 2004

### Publicatie series

Naam Lecture Notes in Computer Science 3111 0302-9743

## Vingerafdruk

Duik in de onderzoeksthema's van 'Pointed binary encompassing trees'. Samen vormen ze een unieke vingerafdruk.