# Pointed binary encompassing trees

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)

## Abstract

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.
Original language English 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 Published - 2004

### Publication series

Name Lecture Notes in Computer Science 3111 0302-9743

## Fingerprint

Dive into the research topics of 'Pointed binary encompassing trees'. Together they form a unique fingerprint.