Maximizing maximal angles for plane straight-line graphs

O. Aichholzer, T. Hackl, M. Hoffmann, C. Huemer, A. Pór, F. Santos, B. Speckmann, B. Vogtenhuber

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

7 Citaten (Scopus)
78 Downloads (Pure)

Samenvatting

Let G¿=¿(S, E) be a plane straight-line graph on a finite point set in general position. The incident angles of a point p¿¿¿S in G are the angles between any two edges of G that appear consecutively in the circular order of the edges incident to p. A plane straight-line graph is called ¿-open if each vertex has an incident angle of size at least ¿. In this paper we study the following type of question: What is the maximum angle ¿ such that for any finite set of points in general position we can find a graph from a certain class of graphs on S that is ¿-open? In particular, we consider the classes of triangulations, spanning trees, and paths on S and give tight bounds in most cases.
Originele taal-2Engels
TitelProceedings of the 10th International Workshop on Algorithms and Data Structures (WADS 2007) 15-17 August 2007, Halifax, Nova Scotia, Canada
RedacteurenF. Dehne, J.R. Sack, N. Zeh
Plaats van productieBerlin
UitgeverijSpringer
Pagina's458-469
ISBN van geprinte versie978-3-540-73948-7
DOI's
StatusGepubliceerd - 2007
Evenement10th International Symposium on Algorithms and Data Structures (WADS 2007) - Halifax, Canada
Duur: 15 aug 200717 aug 2007
Congresnummer: 10

Publicatie series

NaamLecture Notes in Computer Science
Volume4619
ISSN van geprinte versie0302-9743

Congres

Congres10th International Symposium on Algorithms and Data Structures (WADS 2007)
Verkorte titelWADS 2007
Land/RegioCanada
StadHalifax
Periode15/08/0717/08/07
AnderWADS 2007, Halifax, Nova Scotia, Canada

Vingerafdruk

Duik in de onderzoeksthema's van 'Maximizing maximal angles for plane straight-line graphs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit