A study of the LMT-skeleton

Siu Wing Cheng; Naoki Katoh; Manabu Sugai

doi:10.1007/bfb0009502

A study of the LMT-skeleton

Siu Wing Cheng, Naoki Katoh, Manabu Sugai

Department of Computer Science and Engineering

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

9 Citations (Scopus)

Abstract

We present improvements in finding the LMT-skeleton, which is a subgraph of all minimum weight triangulations, independently proposed by Belleville et al, and Dickerson and Montague. Our improvements consist of: (1) A criteria is proposed to identify edges in all minimum weight triangulations, which is a relaxation of the definition of local minimality used in Dickerson and Montague's method to find the LMTskeleton; (2) A worst-Case efficient algorithm is presented for performing one pass of Dickerson and Moutague's method (with our new criteria); (3) Improvements in the implementation that may lead to substantial space reduction for uniformly distributed point sets.

Original language	English
Title of host publication	Algorithms and Computation - 7th International Symposium, ISAAC 1996, Proceedings
Editors	Tetsuo Asano, Yoshihide Igarashi, Hiroshi Nagamochi, Satoru Miyano, Subhash Suri
Publisher	Springer Verlag
Pages	256-265
Number of pages	10
ISBN (Print)	3540620486, 9783540620488
DOIs	https://doi.org/10.1007/bfb0009502
Publication status	Published - 1996
Event	7th International Symposium on Algorithms and Computation, ISAAC 1996 - Osaka, Japan Duration: 16 Dec 1996 → 18 Dec 1996

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1178
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	7th International Symposium on Algorithms and Computation, ISAAC 1996
Country/Territory	Japan
City	Osaka
Period	16/12/96 → 18/12/96

Bibliographical note

Publisher Copyright:
© 1996 Springer-Verlag. All rights reserved.

Access to Document

10.1007/bfb0009502

Cite this

Cheng, S. W., Katoh, N., & Sugai, M. (1996). A study of the LMT-skeleton. In T. Asano, Y. Igarashi, H. Nagamochi, S. Miyano, & S. Suri (Eds.), Algorithms and Computation - 7th International Symposium, ISAAC 1996, Proceedings (pp. 256-265). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1178). Springer Verlag. https://doi.org/10.1007/bfb0009502

Cheng, Siu Wing ; Katoh, Naoki ; Sugai, Manabu. / A study of the LMT-skeleton. Algorithms and Computation - 7th International Symposium, ISAAC 1996, Proceedings. editor / Tetsuo Asano ; Yoshihide Igarashi ; Hiroshi Nagamochi ; Satoru Miyano ; Subhash Suri. Springer Verlag, 1996. pp. 256-265 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{46a766e72a27490c8329b85d4b2afe69,

title = "A study of the LMT-skeleton",

abstract = "We present improvements in finding the LMT-skeleton, which is a subgraph of all minimum weight triangulations, independently proposed by Belleville et al, and Dickerson and Montague. Our improvements consist of: (1) A criteria is proposed to identify edges in all minimum weight triangulations, which is a relaxation of the definition of local minimality used in Dickerson and Montague's method to find the LMTskeleton; (2) A worst-Case efficient algorithm is presented for performing one pass of Dickerson and Moutague's method (with our new criteria); (3) Improvements in the implementation that may lead to substantial space reduction for uniformly distributed point sets.",

author = "Cheng, \{Siu Wing\} and Naoki Katoh and Manabu Sugai",

note = "Publisher Copyright: {\textcopyright} 1996 Springer-Verlag. All rights reserved.; 7th International Symposium on Algorithms and Computation, ISAAC 1996 ; Conference date: 16-12-1996 Through 18-12-1996",

year = "1996",

doi = "10.1007/bfb0009502",

language = "English",

isbn = "3540620486",

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

publisher = "Springer Verlag",

pages = "256--265",

editor = "Tetsuo Asano and Yoshihide Igarashi and Hiroshi Nagamochi and Satoru Miyano and Subhash Suri",

booktitle = "Algorithms and Computation - 7th International Symposium, ISAAC 1996, Proceedings",

}

Cheng, SW, Katoh, N & Sugai, M 1996, A study of the LMT-skeleton. in T Asano, Y Igarashi, H Nagamochi, S Miyano & S Suri (eds), Algorithms and Computation - 7th International Symposium, ISAAC 1996, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1178, Springer Verlag, pp. 256-265, 7th International Symposium on Algorithms and Computation, ISAAC 1996, Osaka, Japan, 16/12/96. https://doi.org/10.1007/bfb0009502

A study of the LMT-skeleton. / Cheng, Siu Wing; Katoh, Naoki; Sugai, Manabu.
Algorithms and Computation - 7th International Symposium, ISAAC 1996, Proceedings. ed. / Tetsuo Asano; Yoshihide Igarashi; Hiroshi Nagamochi; Satoru Miyano; Subhash Suri. Springer Verlag, 1996. p. 256-265 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1178).

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

TY - GEN

T1 - A study of the LMT-skeleton

AU - Cheng, Siu Wing

AU - Katoh, Naoki

AU - Sugai, Manabu

PY - 1996

Y1 - 1996

N2 - We present improvements in finding the LMT-skeleton, which is a subgraph of all minimum weight triangulations, independently proposed by Belleville et al, and Dickerson and Montague. Our improvements consist of: (1) A criteria is proposed to identify edges in all minimum weight triangulations, which is a relaxation of the definition of local minimality used in Dickerson and Montague's method to find the LMTskeleton; (2) A worst-Case efficient algorithm is presented for performing one pass of Dickerson and Moutague's method (with our new criteria); (3) Improvements in the implementation that may lead to substantial space reduction for uniformly distributed point sets.

AB - We present improvements in finding the LMT-skeleton, which is a subgraph of all minimum weight triangulations, independently proposed by Belleville et al, and Dickerson and Montague. Our improvements consist of: (1) A criteria is proposed to identify edges in all minimum weight triangulations, which is a relaxation of the definition of local minimality used in Dickerson and Montague's method to find the LMTskeleton; (2) A worst-Case efficient algorithm is presented for performing one pass of Dickerson and Moutague's method (with our new criteria); (3) Improvements in the implementation that may lead to substantial space reduction for uniformly distributed point sets.

UR - https://openalex.org/W1558597311

UR - https://www.scopus.com/pages/publications/84990205927

U2 - 10.1007/bfb0009502

DO - 10.1007/bfb0009502

M3 - Conference Paper published in a book

SN - 3540620486

SN - 9783540620488

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

SP - 256

EP - 265

BT - Algorithms and Computation - 7th International Symposium, ISAAC 1996, Proceedings

A2 - Asano, Tetsuo

A2 - Igarashi, Yoshihide

A2 - Nagamochi, Hiroshi

A2 - Miyano, Satoru

A2 - Suri, Subhash

PB - Springer Verlag

T2 - 7th International Symposium on Algorithms and Computation, ISAAC 1996

Y2 - 16 December 1996 through 18 December 1996

ER -

Cheng SW, Katoh N, Sugai M. A study of the LMT-skeleton. In Asano T, Igarashi Y, Nagamochi H, Miyano S, Suri S, editors, Algorithms and Computation - 7th International Symposium, ISAAC 1996, Proceedings. Springer Verlag. 1996. p. 256-265. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/bfb0009502

A study of the LMT-skeleton

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this