Farthest segments and extremal triangles spanned by points in R-3
Given a set S of n points in R-3 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 0(n log n) time, O(n) space algorithm, matching the time and space complexities of the planar version. The algorithm is optimal in the algebraic decision tree model. We further prove that the minimum area triangle spanned by S can be found in O(n(2.4) log(0(1)) n) time and space, and the maximum area triangle spanned by S can be found in 0 (h(2.4) log(0(1))) h + n log n) time and O(h(2.4) log(0(1)) h + n) space, where h is the number of vertices of the convex hull of S (h = n in the worst case). (c) 2009 Elsevier B.V. All rights reserved.
farthest line segment computational geometry largest triangle smallest triangle