Compatible Paths on Labelled Point Sets

Abstract

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.

arXiv commentA preliminary version of the paper was presented at the 30th Canadian Conference on Computational Geometry (CCCG 2018)

Cited by in corpus (1)

• On Compatible Matchings