@inproceedings{d7919a4ac5f446f6ba4660e842668050,

title = "Computing farthest neighbors on a convex polytope",

abstract = "Let N be a set of n points in convex position in ℝ3. The farthest-point Voronoi diagram of N partitions ℝ3 into n convex cells. We consider the intersection G(N) of the diagram with the boundary of the convex hull of N. We give an algorithm that computes an implicit representation of G(N) in expected O(n log2 n) time. More precisely, we compute the combinatorial structure of G(N), the coordinates of its vertices, and the equation of the plane defining each edge of G(N). The algorithm allows us to solve the all-pairs farthest neighbor problem for N in expected time O(n log2 n), and to perform farthest-neighbor queries on N in O(log2 n) time with high probability. This can be applied to find a Euclidean maximum spanning tree and a diameter 2-clustering of N in expected O(n log4 n) time.",

author = "Otfried Cheong and Shin, {Chan Su} and Antoine Vigneron",

year = "2001",

month = jan,

day = "1",

language = "English (US)",

isbn = "9783540424949",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "159--169",

editor = "Jie Wang",

booktitle = "Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings",

address = "Germany",

note = "7th Annual International Conference on Computing and Combinatorics, COCOON 2001 ; Conference date: 20-08-2001 Through 23-08-2001",

}