Enumerating Triangulations for Arbitrary Configurations of Points and for Products of Two Simplices
Fumihiko Takeuchi, Hiroshi Imai, Keiko Imai · Institutional Repositories DataBase (IRDB) · 1997
We propose two algorithms to enumerate triangulations. These algorithms enumerate all triangulations, regular or not, for arbitrary configurations of points in any dimensions. Our first algorithm characterizes triangulations as maximal independent sets of the intersection graph. This graph has the maximal dimensional simplices of the given point configuration as vertices, and edges between two simplices whose intersection is not a face for at least one of them. We enumerate the maximal independent sets of this graph, which form a superset of triangulations. The algorithm runs in time proportional to the size of this superset and requires memory only of the size of a triangulation. Our second algorithm enumerates the independent sets of the intersection graph whose interior is connected. These sets also form a superset of triangulations. This algorithm runs in time proportional to the size of this superset and requires memory twice the size of a triangulation. We are also interested in ...