Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Lutz Kettner
Created
04/16/2003 06:36:39 PM
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section