Efficient algorithms for computing the maximum distance between two finite planar sets |
| |
Authors: | Binay K Bhattacharya Godfried T Toussaint |
| |
Institution: | McGill University, School of Computer Science, Montreal, Quebec H3A 2K6, Canada |
| |
Abstract: | An 0(n log n) algorithm is presented for computing the maximum euclidean distance between two finite planar sets of n points. When the n points form the vertices of simple polygons this complexity can be reduced to 0(n). The algorithm is empirically compared to the brute-force method as well as an alternate 0(n2) algorithm. Both the 0(n log n) and 0(n2) algorithms run in 0(n) expected time for many underlying distributions of the points. An ?-approximate algorithm can be obtained that runs in worst-case time. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |