论文标题
测试多项式在平面点集的笛卡尔产品上消失的测试：共线性测试和相关问题
Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets: Collinearity Testing and Related Problems
论文作者
论文摘要
我们在代数决策-tree模型中介绍了亚次级算法，用于检测是否存在三个点，属于飞机上的三个集合$ a $ a $ a $ a $ a $ a $ a $ a，$ b $和$ c $，可以满足某个多项方程式或两个等式。这种问题的最著名实例是测试在$ a \ times b \ times c $中存在共线三倍的点，这是一个经典的3sum-hard问题，到目前为止，无论是在（统一的）真实RAM模型中还是在代数决策中，迄今未尝试获得次级次级解决方案的尝试。虽然我们仍然无法在次级时间的时间内完全解决这个问题，但在代数决策-tree模型中，我们获得了这样的解决方案，该模型仅使用$ o（n^{28/15}）$ constant-degreey-degreey多项式符号测试，在两个友好的平面上，这两个平面是仲裁的，这是两个典型的平面。我们的技术是相当通用的，并且适用于许多其他问题，在这些问题中，我们寻求满足单个多项式方程的三重问题，例如，确定$ a \ times b \ times b \ times c $是否包含一个跨越单位三角形的三倍。该结果扩展了Barba \ etal〜（2017）和Chan（2018）的最新工作，其中所有三个套装$ a $，〜$ b $和〜$ c $被认为是一维的。 作为我们技术的第二次应用，我们再次有三个$ n $ point Sets $ a $，$ b $和$ c $在飞机上，我们想确定是否存在三重$（a，b，c）\在A \ times b \ times b \ times b \ times b \ times c $中同时满足两个独立的真实多项方程。例如，这是在复杂平面中测试共线性时的设置，当每个集合$ a $ a $，$ b $，$ c $都位于某些恒定度的代数曲线上。我们表明，这种问题可以通过大约$ o（n^{24/13}）$ contand-Adegree多项式标志测试来解决。
We present subquadratic algorithms, in the algebraic decision-tree model of computation, for detecting whether there exists a triple of points, belonging to three respective sets $A$, $B$, and $C$ of points in the plane, that satisfy a certain polynomial equation or two equations. The best known instance of such a problem is testing for the existence of a collinear triple of points in $A\times B\times C$, a classical 3SUM-hard problem that has so far defied any attempt to obtain a subquadratic solution, whether in the (uniform) real RAM model, or in the algebraic decision-tree model. While we are still unable to solve this problem, in full generality, in subquadratic time, we obtain such a solution, in the algebraic decision-tree model, that uses only roughly $O(n^{28/15})$ constant-degree polynomial sign tests, for the special case where two of the sets lie on two respective one-dimensional curves and the third is placed arbitrarily in the plane. Our technique is fairly general, and applies to many other problems where we seek a triple that satisfies a single polynomial equation, e.g., determining whether $A\times B\times C$ contains a triple spanning a unit-area triangle. This result extends recent work by Barba \etal~(2017) and by Chan (2018), where all three sets $A$,~$B$, and~$C$ are assumed to be one-dimensional. As a second application of our technique, we again have three $n$-point sets $A$, $B$, and $C$ in the plane, and we want to determine whether there exists a triple $(a,b,c) \in A\times B\times C$ that simultaneously satisfies two independent real polynomial equations. For example, this is the setup when testing for collinearity in the complex plane, when each of the sets $A$, $B$, $C$ lies on some constant-degree algebraic curve. We show that problems of this kind can be solved with roughly $O(n^{24/13})$ constant-degree polynomial sign tests.
