Complex collinearities

Definitions and mathematical statement

Let $P=\{p_1,\ldots,p_n\}\subset{\mathbb{C}}^2$ with $p_i=(x_i,y_i)$. A complex affine line is a set $a+{\mathbb{C}} b=\{a+tb:t\in{\mathbb{C}}\}$ for $b\ne0$. For three distinct points, complex collinearity is equivalent to \[ \det\begin{pmatrix} 1&x_i&y_i\\1&x_j&y_j\\1&x_k&y_k \end{pmatrix}=0. \] This is collinearity on a complex one-dimensional affine subspace, not collinearity on a real line in ${\mathbb{R}}^4$.

Algorithmic question. Given $n$ points in ${\mathbb{C}}^2$, determine in $O(n^2)$ time whether there are three distinct points on a complex line, or prove a quadratic lower bound for this decision problem. The source reports an $O(n^2\log n)$ algorithm. The requested upper bound omits the logarithmic factor; the lower-bound alternative means $\Omega(n^2)$ in an intended computational model. These are alternative requested advances, not a supplied matching upper/lower theorem.

No coordinate representation, arithmetic/bit cost model, allowed algebraic tests, randomized-error convention, or worst-case versus expected-time convention is specified. An exact-arithmetic real/complex RAM is a possible interpretation, but it is not imposed. The set notation above uses distinct input points; the treatment of duplicate coordinates in a listed input is also not supplied.

The research summary labels the problem partially solved and mentions 3SUM-type hardness and a "sub-quadratic-with-log" algorithm without an actual running-time formula or citation. This phrase cannot be identified with the explicitly stated $O(n^2\log n)$ bound, which is not subquadratic. No faster algorithm, unconditional lower bound, or precise 3SUM reduction is authenticated by the record. The background warns that Erickson's pages have not been systematically updated since 2001.

Short English statement

Decide in quadratic time whether a set of points in ${\mathbb{C}}^2$ contains three points on a complex affine line, or establish a quadratic lower bound in a specified model. The source gives $O(n^2\log n)$ time; its later summary is vague about claimed progress and the computational model is missing.

Sources

• Local UnsolvedMath registry, permanent ID 3800012, source code catalogue entry, "Complex collinearities"; attribution field: Jeff Erickson and cited proposers. Supplied status partially solved, classification PARTIAL-PROGRESS, updated 2026-08-06.
• Erickson, Open Problems in Computational Geometry, item "Complex collinearities," supplied index https://jeffe.cs.illinois.edu/open/. Reported HTML extraction and access: 2026-07-29. The source explicitly warns that its pages have not been systematically updated since 2001. Rights: NEEDS_REVIEW; public access verified but redistribution permission not established.
• The $O(n^2\log n)$ algorithm and the summary's faster-algorithm/3SUM comments have no supplied primary-paper citations or precise reduction statements.