Compatible Paths on Labelled Point Sets

04/16/2020
by   Elena Arseneva, et al.
0

Let P and Q be finite point sets of the same cardinality in ℝ^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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset