On the All-Farthest-Segments problem for a planar set of points |
| |
Authors: | Asish Mukhopadhyay Samidh Chatterjee |
| |
Affiliation: | School of Computer Science, University of Windsor, Windsor, Ontario, Canada |
| |
Abstract: | In this note, we outline a very simple algorithm for the following problem: Given a set S of n points p1,p2,p3,…,pn in the plane, we have O(n2) segments implicitly defined on pairs of these n points. For each point pi, find a segment from this set of implicitly defined segments that is farthest from pi. The time complexity of our algorithm is in O(nh+nlogn), where n is the number of input points, and h is the number of vertices on the convex hull of S. |
| |
Keywords: | Algorithms Computational geometry Analysis of algorithms Design of algorithms Computational complexity |
本文献已被 ScienceDirect 等数据库收录! |
|