2008年7月
Enumerating constrained non-crossing minimally rigid frameworks
DISCRETE & COMPUTATIONAL GEOMETRY
- ,
- ,
- ,
- ,
- 巻
- 40
- 号
- 1
- 開始ページ
- 31
- 終了ページ
- 46
- 記述言語
- 英語
- 掲載種別
- DOI
- 10.1007/s00454-007-9026-x
- 出版者・発行元
- SPRINGER
In this paper we present an algorithm for enumerating without repetitions all the non-crossing generically minimally rigid bar-and-joint frameworks under edge constraints, which we call constrained non-crossing Laman frameworks, on a given set of n points in the plane. Our algorithm is based on the reverse search paradigm of Avis and Fukuda. It generates each output graph in O(n(4)) time and O(n) space, or, with a slightly different implementation, in O(n(3)) time and O(n(2)) space. In particular, we obtain that the set of all the constrained non-crossing Laman frameworks on a given point set is connected by flips which preserve the Laman property.
- リンク情報
-
- DOI
- https://doi.org/10.1007/s00454-007-9026-x
- Web of Science
- https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000258276300002&DestApp=WOS_CPL
- URL
- http://www.scopus.com/inward/record.url?partnerID=HzOxMe3b&scp=49249133486&origin=inward
- ID情報
-
- DOI : 10.1007/s00454-007-9026-x
- ISSN : 0179-5376
- SCOPUS ID : 49249133486
- Web of Science ID : WOS:000258276300002