Finding segments and triangles spanned by points in R³

Given a set S of n points in R³ we consider finding the farthest line segment spanned by S from a query point q given as part of the input, and finding the minimum and maximum area triangles spanned by S. For the farthest line segment problem we give an O(nlog₂n) time, O(n) space algorithm, matching the time and space complexities of the planar version. The algorithm is optimal in the algebrai deision tree model. We further prove that the minimum area triangle spanned by S an be found in O(n^2.4log₂^O(1)n) time and space, and the maximum area triangle spanned by S an be found in O(h^2.4log₂^O(1)h + nlog₂n) time and O(h^2.4log₂^O(1)h + n) space, where h is the number of vertices of the convex hull of S (h = n in the worst case).

Download paper here