Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Mathematics
Enumerating Constrained Non-Crossing Minimally Rigid Frameworks, David Avis, Naoki Katoh, Makoto Ohsaki, Ileana Streinu, Shin-Ichi Tanigawa
Enumerating Constrained Non-Crossing Minimally Rigid Frameworks, David Avis, Naoki Katoh, Makoto Ohsaki, Ileana Streinu, Shin-Ichi Tanigawa
Computer Science: Faculty Publications
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(n4) time and O(n) space, or, with a slightly different implementation, in O(n3) time and O(n2) space. In particular, we obtain that the set of all the constrained non-crossing Laman …