# Finding segments and triangles spanned by points in R^{3}

Published in *CCCG 2007*, 2007

Recommended citation: __http://cccg.ca/proceedings/2007/01a3.pdf__

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 *O(nlog _{2}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*time and space, and the maximum area triangle spanned by

^{2.4}log_{2}^{O(1)}n)*S*an be found in

*O(h*time and

^{2.4}log_{2}^{O(1)}h + nlog_{2}n)*O(h*space, where

^{2.4}log_{2}^{O(1)}h + n)*h*is the number of vertices of the convex hull of

*S*(

*h*=

*n*in the worst case).