Subquadratic Encodings for Point Configurations
Subquadratic Encodings for Point Configurations
复制标题
点配置的次二次编码
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Aurélien Ooms
中科院分区：
文献类型：
--
作者：
J. Cardinal;Timothy M. Chan;J. Iacono;S. Langerman;Aurélien Ooms
对于处理平面上点集的大多数算法，输入所携带的唯一相关信息是点的组合配置：集合中每个点的方向（顺时针，逆时针或共线）。这些信息称为点集的序类型。在对偶中，可实现序类型和抽象序类型是线性排列和伪线性排列的组合类比。在文献中，我们经常为了简单而分析实RAM模型中的算法，而忽略了这样一个事实，即我们所知道的计算机在没有某种编码的情况下无法处理任意的真实的数字。已知用某个实现点集的整数坐标编码一个序类型在某些情况下会产生双指数坐标。其他已知的编码可以实现二次空间或快速方向查询，但不能同时实现两者。在这篇文章中，我们给出了一个紧凑的编码抽象顺序类型，允许有效的查询任何三元组的方向：编码使用O（n^2）位和方向查询需要O（log n）的时间在字RAM模型。这种编码对于抽象顺序类型是空间最优的。我们展示了如何将编码缩短到O（n^2（loglog n）^2 / log n）位，为可实现的顺序类型，给出了第一个次二次编码的顺序类型与快速方向查询。我们进一步完善我们的编码，以达到O（log n/loglog n）的查询时间，而不炸毁的空间需求。在可实现的情况下，我们表明，所有这些编码可以有效地计算。最后，我们将所得结果推广到高维点构型的编码问题。
For most algorithms dealing with sets of points in the plane, the only relevant information carried by the input is the combinatorial configuration of the points: the orientation of each triple of points in the set (clockwise, counterclockwise, or collinear). This information is called the order type of the point set. In the dual, realizable order types and abstract order types are combinatorial analogues of line arrangements and pseudoline arrangements. Too often in the literature we analyze algorithms in the real-RAM model for simplicity, putting aside the fact that computers as we know them cannot handle arbitrary real numbers without some sort of encoding. Encoding an order type by the integer coordinates of some realizing point set is known to yield doubly exponential coordinates in some cases. Other known encodings can achieve quadratic space or fast orientation queries, but not both. In this contribution, we give a compact encoding for abstract order types that allows efficient query of the orientation of any triple: the encoding uses O(n^2) bits and an orientation query takes O(log n) time in the word-RAM model. This encoding is space-optimal for abstract order types. We show how to shorten the encoding to O(n^2 (loglog n)^2 / log n) bits for realizable order types, giving the first subquadratic encoding for those order types with fast orientation queries. We further refine our encoding to attain O(log n/loglog n) query time without blowing up the space requirement. In the realizable case, we show that all those encodings can be computed efficiently. Finally, we generalize our results to the encoding of point configurations in higher dimension.