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 languageEnglish
Title of host publicationAlgorithm Theory - SWAT 2004 (Proceedings 9th Scandinavian Workshop on Algorithm Theory, Humlebaek, Denmark, July 8-10, 2004)
EditorsT. Hagerup, J. Katajainen
Place of PublicationBerlin
PublisherSpringer
Pages442-454
ISBN (Print)3-540-22339-8
DOIs
Publication statusPublished - 2004

Publication series

NameLecture Notes in Computer Science
Volume3111
ISSN (Print)0302-9743

Fingerprint

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

Cite this