我目前正在研究一个 2D 有限元代码，其网格包含在某些发生跳跃的接口处的重复节点。为了建立适当的线性系统，我必须获取网格连接信息和网格节点的位置，并对其进行操作以确定哪些元素跨界面相邻。
为了了解潜在的串行运行时缩放，我用节点数（或自由度数）表示了每个算法的所有渐近复杂性，因为这是一个自然的复杂性度量。我可以使用关于平面图的众所周知的事实来做到这一点。
我希望能够将这些算法扩展到 3D 网格，并且我想了解它们在节点数量方面的复杂性。我也确信 3D 网格不一定是平面图。是否存在根据网格节点数限制 3D 网格的边数、面数和元素数的结果？假设一个单纯的网格很好；六面体网格的结果也会很有趣。
我确信我所做的一切都不是新的。我只是不太使用网格，所以我不知道在哪里寻找结果。
单纯曲面细分的复杂性， 为了不幸的是，它不是线性的。
一般来说，一个简单的镶嵌为了顶点可以有最坏情况下的d-单纯形。类似的结果存在于低维面.
基于四面体网格的实践经验不过，我认为大多数四面体网格表现出线性复杂性是普遍接受的，例如. 考虑到您几乎可以肯定处理的是高质量的有限元样式网格，而不是计算几何中的一些人为的病态示例，我想在您的案例中，在实践中会观察到线性复杂性。
您可能有兴趣查看Jonathan Shewchuk关于 (Delaunay) 镶嵌的研究。上面引用的结果出现在Shewchuk、Cheng 和 Dey最近的著作Delaunay Mesh Generation中——它是网格生成理论的一个很好的参考！
对于二维和三角形，有传统的欧拉公式：
为了边缘，面孔，和顶点（假设没有孔）。
在四面体的 3D 中，有一个类似的公式：
一切都如上过头。这全部取自 Carey 的书Computational Grids , Taylor & Francis, 1997 pp. 86 和 90。
不过，正如 Darren 的回答所指出的，这可能会导致 3D 中的一些复杂性，尽管许多网格都很好。