2002年12月
Enumerating triangulations in general dimensions
INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS
- ,
- ,
- ,
- 巻
- 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.
- リンク情報
- ID情報
-
- DOI : 10.1142/S0218195902000980
- ISSN : 0218-1959
- Web of Science ID : WOS:000180213600002