论文标题
标记点集的兼容路径
Compatible Paths on Labelled Point Sets
论文作者
论文摘要
令$ p $和$ q $是$ \ mathbb {r}^2 $的同一基数的有限点集，每个标签从$ 1 $到$ n $。两个非交叉几何图$ g_p $和$ g_q $ spanning $ p $和$ q $，如果对于$ g_p $中的每个face $ f $ in $ g_p $中的每个face $ f $，则在$ g_q $中存在相应的面孔，并且在$ f $中的边界上顺时针订购了同一顺时针。特别是，$ g_p $和$ g_q $必须是同一连接的$ n $ vertex图的直线嵌入。 确定两个标记的点集是否允许兼容的几何路径是NP完整的。我们给出多项式时间算法，以找到兼容的路径或报告在三种情况下不存在：$ o（n）$ $（$ o（n）$时间的时间； $ O（n^2）$时间用于两个简单的多边形，其中路径仅限于封闭的多边形内；如果路径被限制为单调，则$ o（n^2 \ log n）$ for Points的时间。
Let $P$ and $Q$ be finite point sets of the same cardinality in $\mathbb{R}^2$, each labelled from $1$ to $n$. Two noncrossing geometric graphs $G_P$ and $G_Q$ spanning $P$ and $Q$, respectively, are called compatible if for every face $f$ in $G_P$, there exists a corresponding face in $G_Q$ with the same clockwise ordering of the vertices on its boundary as in $f$. In particular, $G_P$ and $G_Q$ must be straight-line embeddings of the same connected $n$-vertex graph. Deciding whether two labelled point sets admit compatible geometric paths is known to be NP-complete. We give polynomial-time algorithms to find compatible paths or report that none exist in three scenarios: $O(n)$ time for points in convex position; $O(n^2)$ time for two simple polygons, where the paths are restricted to remain inside the closed polygons; and $O(n^2 \log n)$ time for points in general position if the paths are restricted to be monotone.
