MPI-INF D1 Publications: Journal Article: Tight Degree Bounds for Pseudo-triangulations of Points

Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2023) | last year (2022) | two years ago (2021) | Notes URL

Action:

Options:

Goto entry point

Author, Editor(s)

Author(s):

Kettner, Lutz
Kirkpatrick, David
Mantler, Andrea
Snoeyink, Jack
Speckmann, Bettina
Takeuchi, Fumihiko

dblp
dblp
dblp
dblp
dblp
dblp

BibTeX cite key*:

Kettner2003DegreeBound

Title

Title*:

Tight Degree Bounds for Pseudo-triangulations of Points

Journal

Journal Title*:	Computational Geometry - Theory and Applications	Journal's URL:	http://www.elsevier.nl/locate/comgeo
Download URL for the article:		Language:	English

Publisher

Publisher's Name:	Elsevier	Publisher's URL:	http://www.elsevier.nl/
Publisher's Address:	Amsterdam, The Netherlands	ISSN:	0925-7721

Vol, No, pp, Date

Volume*:	25	Number:	1-2
Publishing Date:	2003
Pages*:	3-12	Number of VG Pages:	24
Page Start:		Page End:
Sequence Number:		DOI:

Note, Abstract, ©

Note:
(LaTeX) Abstract:	We show that every set of $n$ points in general position has a minimum pseudo-triangulation whose maximum vertex degree is five. In addition, we demonstrate that every point set in general position has a minimum pseudo-triangulation whose maximum face degree is four (i.e.\ each interior face of this pseudo-triangulation has at most four vertices). Both degree bounds are tight. Minimum pseudo-triangulations realizing these bounds (individually but not jointly) can be constructed in $O(n \log n)$ time.
URL for the Abstract:	http://www.mpi-sb.mpg.de/~kettner/pub/pseudot_degree_cgta_03_a.html
Categories, Keywords:	Geometry
HyperLinks / References / URLs:
Copyright Message:
Personal Comments:
Download Access Level:	Public

Correlation

MPG Unit:	Max-Planck-Institut für Informatik

MPG Subunit:	Algorithms and Complexity Group
Audience:	popular
Appearance:	MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@ARTICLE{Kettner2003DegreeBound,
AUTHOR = {Kettner, Lutz and Kirkpatrick, David and Mantler, Andrea and Snoeyink, Jack and Speckmann, Bettina and Takeuchi, Fumihiko},
TITLE = {Tight Degree Bounds for Pseudo-triangulations of Points},
JOURNAL = {Computational Geometry - Theory and Applications},
PUBLISHER = {Elsevier},
YEAR = {2003},
NUMBER = {1-2},
VOLUME = {25},
PAGES = {3--12},
ADDRESS = {Amsterdam, The Netherlands},
ISBN = {0925-7721},
}

Entry last modified by Lutz Kettner, 03/02/2010

Edit History (please click the blue arrow to see the details)

	Editor(s) Lutz Kettner	Created 04/16/2003 18:36:39
Revisions 3. 2. 1. 0.	Editor(s) Lutz Kettner Christine Kiesel Lutz Kettner Lutz Kettner	Edit Dates 01/24/2005 03:05:03 PM 15.06.2004 17:57:44 04/16/2003 06:46:14 PM 04/16/2003 06:36:39 PM

Attachment Section