A geometric graph is a combinatorial graph, endowed with a geometry that is inherited from its embedding in a Euclidean space. Formulation of a meaningful measure of (dis-)similarity in both the combinatorial and geometric structures of two such geometric graphs is a challenging problem in pattern recognition. We study two notions of distance measures for geometric graphs, called the geometric edit distance (GED) and geometric graph distance (GGD). While the former is based on the idea of editing one graph to transform it into the other graph, the latter is inspired by inexact matching of the graphs. For decades, both notions have been lending themselves well as measures of similarity between attributed graphs. If used without any modification, however, they fail to provide a meaningful distance measure for geometric graphs -- even cease to be a metric. We have curated their associated cost functions for the context of geometric graphs. Alongside studying the metric properties of GED and GGD, we investigate how the two notions compare. We further our understanding of the computational aspects of GGD by showing that the distance is $\mathcal{NP}$-hard to compute, even if the graphs are planar and arbitrary cost coefficients are allowed.
翻译:几何图形是一个组合图, 具有从嵌入一个 Euclidean 空间所继承的几何图。 在两个这样的几何图形的组合和几何结构中, 设计一个有意义的( 不同) 相似度( 不同) 是一个具有挑战性的特征识别问题。 我们研究了几何图形的两种距离测量概念, 称为几何编辑距离( GED) 和几何图形距离( GGD) 。 前者以编辑一个图形将其转换为另一个图形的构想为基础, 而后者则由图表不精确的匹配所启发。 几十年来, 两种概念都是自己出借的, 以及被归属的图表之间的相似度度。 但是, 如果不加修改, 它们无法为几何图形提供有意义的距离测量度度度( 甚至不再是一个计量标准 ) 。 我们已经为几何图形的背景定义了它们相关的成本函数。 我们除了研究 GED 和 GGD 的衡量属性外, 我们研究这两个概念是如何比较的。 我们进一步理解GGD的计算方面, 显示即使距离为 美元和 基数的计算成本, 也是 。