The Complexity of Order Type Isomorphism
The Complexity of Order Type Isomorphism
复制标题
订单类型同构的复杂性
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Stefanie Wuhrer
中科院分区：
文献类型：
--
作者：
G. Aloupis;J. Iacono;S. Langerman;Özgür Özkan;Stefanie Wuhrer
Rd 中点集的顺序类型将点的每个 (d+1) 元组映射到其方向（例如，R2 中的顺时针或逆时针）。如果存在从 X 到 Y 的映射 f，其中 X 的每个 (d+1) 元组 (a1, a2, ..., ad+1) 和 Y 中的相应元组 (f(a1), f(a2), ..., f(ad+1)) 具有相同的方向，则两个点集 X 和 Y 具有相同的顺序类型。在本文中，我们研究了确定两个点集是否具有相同顺序类型的复杂性。我们为此任务提供了一个 O(nd) 算法，从而改进了 Goodman 和 Pollack (1983) 的 O(n⌊3d/2⌋) 算法。该算法仅使用订单类型查询，也适用于抽象订单类型（或非循环导向拟阵）。如果算法仅使用订单类型查询，则我们的算法在抽象设置和可实现点集方面都是最佳的。
The order type of a point set in Rd maps each (d+1)-tuple of points to its orientation (e.g., clockwise or counterclockwise in R2). Two point sets X and Y have the same order type if there exists a mapping f from X to Y for which every (d+1)-tuple (a1, a2, ..., ad+1) of X and the corresponding tuple (f(a1), f(a2), ..., f(ad+1)) in Y have the same orientation. In this paper we investigate the complexity of determining whether two point sets have the same order type. We provide an O(nd) algorithm for this task, thereby improving upon the O(n⌊3d/2⌋) algorithm of Goodman and Pollack (1983). The algorithm uses only order type queries and also works for abstract order types (or acyclic oriented matroids). Our algorithm is optimal, both in the abstract setting and for realizable points sets if the algorithm only uses order type queries.