MISC

2002年12月

Enumerating triangulations in general dimensions

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS
  • H Imai
  • ,
  • T Masada
  • ,
  • F Takeuchi
  • ,
  • K Imai

12
6
開始ページ
455
終了ページ
480
記述言語
英語
掲載種別
DOI
10.1142/S0218195902000980
出版者・発行元
WORLD SCIENTIFIC PUBL CO PTE LTD

We propose algorithms to enumerate (1) regular triangulations, (2) spanning regular triangulations, (3) equivalence classes of regular triangulations with respect to symmetry, and (4) all triangulations. All of the algorithms are for arbitrary points in general dimension. They work in output-size sensitive time with memory only of several times the size of a triangulation. For the enumeration of regular triangulations, we use the fact by Gel'fand, Zelevinskii and Kapranov that regular triangulations correspond to the vertices of the secondary polytope. We use reverse search technique by Avis and Fukuda, its extension for enumerating equivalence classes of objects, and a reformulation of a maximal independent set enumeration algorithm. The last approach can be extended for enumeration of dissections.

リンク情報
DOI
https://doi.org/10.1142/S0218195902000980
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000180213600002&DestApp=WOS_CPL
ID情報
  • DOI : 10.1142/S0218195902000980
  • ISSN : 0218-1959
  • Web of Science ID : WOS:000180213600002

エクスポート
BibTeX RIS