A PTAS for minimum vertex dilation triangulation of a simple polygon with a constant number of sources of dilation

Rolf Klein; Christos Levcopoulos; Andrzej Lingas

doi:10.1016/j.comgeo.2005.06.004

A PTAS for minimum vertex dilation triangulation of a simple polygon with a constant number of sources of dilation

Rolf Klein, Christos Levcopoulos, Andrzej Lingas

Research output: Contribution to journal › Article › peer-review

Abstract

We design a fully polynomial-time approximation scheme for the problem of finding a triangulation of a simple poly-on with a constant number of sources of dilation that achieves the minimum vertex dilation. (c) 2005 Elsevier B.V. All rights reserved.

Original language	English
Pages (from-to)	28-34
Journal	Computational Geometry
Volume	34
Issue number	1
DOIs	https://doi.org/10.1016/j.comgeo.2005.06.004
Publication status	Published - 2006

Bibliographical note

Special Issue on the Japan Conference on Discrete and Computational Geometry 2004

Subject classification (UKÄ)

Computer Sciences

Free keywords

triangulation
dilation
polynomial-time approximation scheme
polygon

Access to Document

10.1016/j.comgeo.2005.06.004

Cite this

@article{6685d31d84bc419791634a754848fda2,

title = "A PTAS for minimum vertex dilation triangulation of a simple polygon with a constant number of sources of dilation",

abstract = "We design a fully polynomial-time approximation scheme for the problem of finding a triangulation of a simple poly-on with a constant number of sources of dilation that achieves the minimum vertex dilation. (c) 2005 Elsevier B.V. All rights reserved.",

keywords = "triangulation, dilation, polynomial-time approximation scheme, polygon",

author = "Rolf Klein and Christos Levcopoulos and Andrzej Lingas",

note = "Special Issue on the Japan Conference on Discrete and Computational Geometry 2004",

year = "2006",

doi = "10.1016/j.comgeo.2005.06.004",

language = "English",

volume = "34",

pages = "28--34",

journal = "Computational Geometry",

issn = "0925-7721",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - A PTAS for minimum vertex dilation triangulation of a simple polygon with a constant number of sources of dilation

AU - Klein, Rolf

AU - Levcopoulos, Christos

AU - Lingas, Andrzej

N1 - Special Issue on the Japan Conference on Discrete and Computational Geometry 2004

PY - 2006

Y1 - 2006

N2 - We design a fully polynomial-time approximation scheme for the problem of finding a triangulation of a simple poly-on with a constant number of sources of dilation that achieves the minimum vertex dilation. (c) 2005 Elsevier B.V. All rights reserved.

AB - We design a fully polynomial-time approximation scheme for the problem of finding a triangulation of a simple poly-on with a constant number of sources of dilation that achieves the minimum vertex dilation. (c) 2005 Elsevier B.V. All rights reserved.

KW - triangulation

KW - dilation

KW - polynomial-time approximation scheme

KW - polygon

U2 - 10.1016/j.comgeo.2005.06.004

DO - 10.1016/j.comgeo.2005.06.004

M3 - Article

SN - 0925-7721

VL - 34

SP - 28

EP - 34

JO - Computational Geometry

JF - Computational Geometry

IS - 1

ER -

A PTAS for minimum vertex dilation triangulation of a simple polygon with a constant number of sources of dilation

Abstract

Bibliographical note

Subject classification (UKÄ)

Free keywords

Access to Document

Fingerprint

Cite this