A Triangulated Irregular Network (TIN) is a data structure that is usually used for representing and storing monotone geographic surfaces, approximately. In this representation, the surface is approximated by a set of triangular faces whose projection on the XY-plane is a triangulation. The visibility graph of a TIN is a graph whose vertices correspond to the vertices of the TIN and there is an edge between two vertices if their corresponding vertices on TIN see each other, i.e. the segment that connects these vertices completely lies above the TIN. Computing the visibility graph of a TIN and its properties have been considered thoroughly in the literature. In this paper, we consider this problem in reverse: Given a graph G, is there a TIN with the same visibility graph as G? We show that this problem is Complete for Existential Theory of The Reals.
翻译:三角非常规网络( TIN) 是一个数据结构, 通常用来代表和存储单色地理表面。 在这个表示中, 表面被一组三角面相近, 在 XY 平面上投射为三角图。 TIN 的可见度图是一个图, 其顶点与 TIN 的顶点相对应, 如果 tIN 上相应的顶点相见, 则有两个顶点之间的边缘, 即将这些顶点完全连接在 TIN 之上的段。 计算 TIN 的可见度图及其属性在文献中得到了彻底的考虑 。 在本文中, 我们从反向考虑这个问题: 图形G 中看, 是否有与 G 相同的可见度图一样的 TIN? 我们表明, 这个问题对于真实的理论的演化理论来说是完整的 。