On constrained minimum pseudotriangulations

Günter Rote; Cao An Wang; Lusheng Wang; Yinfeng Xu

On constrained minimum pseudotriangulations

Günter Rote, Cao An Wang, Lusheng Wang, Yinfeng Xu

Department of Computer Science

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

12 Citations (Scopus)

Abstract

In this paper, we show some properties of a pseudotriangle and present three combinatorial bounds: the ratio of the size of minimum pseudotriangulation of a point set S and the size of minimal pseudotriangulation contained in a triangulation T, the ratio of the size of the best minimal pseudotriangulation and the worst minimal pseudotriangulation both contained in a given triangulation T, and the maximum number of edges in any settings of S and T. We also present a linear-time algorithm for finding a minimal pseudotriangulation contained in a given triangulation. We finally study the minimum pseudotriangulation containing a given set of non-crossing line segments. © Springer-Verlag Berlin Heidelberg 2003.

Original language	English
Pages (from-to)	445-454
Journal	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2697
Publication status	Published - 2003

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{2112412b1168437d8cb9594e07749a4c,

title = "On constrained minimum pseudotriangulations",

abstract = "In this paper, we show some properties of a pseudotriangle and present three combinatorial bounds: the ratio of the size of minimum pseudotriangulation of a point set S and the size of minimal pseudotriangulation contained in a triangulation T, the ratio of the size of the best minimal pseudotriangulation and the worst minimal pseudotriangulation both contained in a given triangulation T, and the maximum number of edges in any settings of S and T. We also present a linear-time algorithm for finding a minimal pseudotriangulation contained in a given triangulation. We finally study the minimum pseudotriangulation containing a given set of non-crossing line segments. {\textcopyright} Springer-Verlag Berlin Heidelberg 2003.",

author = "G{\"u}nter Rote and Wang, {Cao An} and Lusheng Wang and Yinfeng Xu",

year = "2003",

language = "English",

volume = "2697",

pages = "445--454",

journal = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

issn = "0302-9743",

publisher = "Springer Science and Business Media Deutschland GmbH",

}

On constrained minimum pseudotriangulations. / Rote, Günter; Wang, Cao An; Wang, Lusheng et al.
In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 2697, 2003, p. 445-454.

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

TY - JOUR

T1 - On constrained minimum pseudotriangulations

AU - Rote, Günter

AU - Wang, Cao An

AU - Wang, Lusheng

AU - Xu, Yinfeng

PY - 2003

Y1 - 2003

N2 - In this paper, we show some properties of a pseudotriangle and present three combinatorial bounds: the ratio of the size of minimum pseudotriangulation of a point set S and the size of minimal pseudotriangulation contained in a triangulation T, the ratio of the size of the best minimal pseudotriangulation and the worst minimal pseudotriangulation both contained in a given triangulation T, and the maximum number of edges in any settings of S and T. We also present a linear-time algorithm for finding a minimal pseudotriangulation contained in a given triangulation. We finally study the minimum pseudotriangulation containing a given set of non-crossing line segments. © Springer-Verlag Berlin Heidelberg 2003.

AB - In this paper, we show some properties of a pseudotriangle and present three combinatorial bounds: the ratio of the size of minimum pseudotriangulation of a point set S and the size of minimal pseudotriangulation contained in a triangulation T, the ratio of the size of the best minimal pseudotriangulation and the worst minimal pseudotriangulation both contained in a given triangulation T, and the maximum number of edges in any settings of S and T. We also present a linear-time algorithm for finding a minimal pseudotriangulation contained in a given triangulation. We finally study the minimum pseudotriangulation containing a given set of non-crossing line segments. © Springer-Verlag Berlin Heidelberg 2003.

UR - http://www.scopus.com/inward/record.url?scp=35248859666&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-35248859666&origin=recordpage

M3 - RGC 21 - Publication in refereed journal

SN - 0302-9743

VL - 2697

SP - 445

EP - 454

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ER -

On constrained minimum pseudotriangulations

Abstract

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this