Extremal point queries with lines and line segments and related problems (Q2571215)

Let \(P\) be a set of \(n\) points in \(\mathbb R^d\), for some fixed \(d\geq 3\). The authors consider a number of extremal point query problems, including the computation of the farthest point from a query line, and the computation of the farthest point from each of the lines spanned by the points in \(P\). In \(\mathbb R^3\), a data structure of size \(O(n^{1+\varepsilon})\) is given that can be constructed in time \(O(n^{1+\varepsilon})\) and can report the farthest point of \(P\) from a query line in \(O(n^{2/3+\varepsilon})\) time, where \(\varepsilon > 0\) is a constant that can be arbitrarily small. Applications include sub-cubic time algorithms for fitting a polygonal chain through an indexed set of points in \(\mathbb R^d\), \(d\geq 3\), and sub-quadratic time and space algorithms that computes the minimum or maximum area triangle defined by \(q\) with \(P\setminus\{q\}\), for a given set \(P\) and an anchor point \(q\).