Given a set P of n labeled points in the plane, the radial system of P describes, for each p ∈ P, the radial ordering of the other points around p. This notion is related to the order type of P, which describes the orientation (clockwise or counterclockwise) of every ordered triple of P. Given only the order type of P, it is easy to reconstruct the radial system of P, but the converse is not true. Aichholzer et al. (Reconstructing Point Set Order Types from Radial Orderings, in Proc. ISAAC 2014) defined T(R) to be the set of order types with radial system R and showed that sometimes |T(R)| = n - 1. They give polynomial-time algorithms to compute T(R) when only given R. We describe an optimal O(n~2) time algorithm for computing T(R). The algorithm constructs the convex hulls of all possible point sets with the given radial system, after which sidedness queries on point triples can be answered in constant time. This set of convex hulls can be found in O(n) time. Our results generalize to abstract order types.
展开▼
机译：给定平面中的N标记点的SED，P的径向系统描述了每个P≠P，对P的其他要点的径向排序。该概念与P的顺序类型有关，其描述了每个有序三联人的定向（顺时针或逆时针），只给出了P的顺序类型，它很容易重建P的径向系统，但逆转是不对。 Aichholzer等。 （重建点设置从径向排序的订单类型，在proc中.ISAAC 2014）定义了T（R）是具有径向系统R的订单类型的集合，并显示有时| T（R）| = n - 1.它们给出多项式算法，以计算仅在给定R时计算T（R）。我们描述了用于计算T（R）的最佳O（n〜2）时间算法。该算法构造与给定的径向系统的所有可能点集的凸壳，之后在恒定的时间内可以回答点三元脉上的相似查询。这组凸壳可以在O（n）时间内找到。我们的结果概括为抽象订单类型。
展开▼
