An Epsilon-Net-Based Algorithm for Minimizing Functionals on Complexes

Abstract

we developed an ε-net algorithm for minimizing functionals defined on complexes with a prescribed rank structure. A major challenge in analyzing highly detailed complexes is the rapid growth in computational complexity as the state space increases. To address this problem, we proposed a method for partitioning the state space into ε-net classes and replacing the original complex with a coarsened graph. We grouped rank-zero elements into classes according to a specified metric and constructed classes of higher-rank elements from the classes of their constituent elements. We used lexicographic optimization of the objective functional: we first minimized the number of transitions between ε-classes and then minimized the route length in the original complex. We demonstrated the algorithm on a polyhedral complex representing an actual building and applied it to routing problems. The model included the building’s nodes, edges, faces, and three-dimensional cells. Our software implementation supports the construction of the original and factorized graphs, the computation of conventional, ε-class-based, and lexicographically optimal routes, and their visual comparison. The proposed approach can also be applied to other functionals defined on complexes, provided that a suitable proximity measure and rules for forming classes are specified.