  Polynomial reconstruction on Cartesian grids is a key problem in developing
finite difference methods as well as in many other engineering applications,
yet it is still an open problem how to construct for a finite subset $K$ of
$\mathbb{Z}^{\textsf{D}}$ a lattice $\mathcal{T}\subset K$ so that multivariate
polynomial interpolation on this lattice is unisolvent. In this work, we solve
this open problem of poised lattice generation (PLG) via an interdisciplinary
research of approximation theory, abstract algebra, and artificial intelligence
(AI). Specifically, we focus on the triangular lattices in approximation
theory, study group actions of permutations upon triangular lattices, prove an
isomorphism between the group of permutations and that of triangular lattices,
and dynamically organize the AI state space of permutations so that a
depth-first search of poised lattices has optimal efficiency. Based on this
algorithm, we further develop the PLG finite difference method that retains the
simplicity of Cartesian grids yet overcomes the disadvantage of legacy finite
difference methods in handling irregular geometries. Results of various
numerical tests demonstrate the effectiveness of our algorithm and the
simplicity, efficiency, and fourth-order accuracy of the PLG finite difference
method.
