Both Okabe and Miller, and Chin and Wang, give O(m1 + m2) optimal algorithms for distance between a single pair. On closer examination, however, neither address the many pairs problem. There must be some conventional computational geometry approach using sweep algorithms or something to reduce the final complexity below O(m * n^2) where n is number of polygons. Denis
Hi, I am not very familiar with the m.in.e00 command in GRASS. Is the
point
to compute an all pairs min distance between all polygons in a set or just the min distance between two polygons or something inbetween.
If
it is an all pairs problem then the optimum is O((n*m)^2) as Denis
White
states below. If it is inbetween we can do much better. A potentially easier implementation than the Okabe Miller approach is to just use a good data structure on the bounding boxes of the polygons and filter
the
returned list from a range query with a bruteforce menthod. That may
be
efficient enough. On calculating the min (or max) distance between two polygons one could probably do much better than O((m1*m2)^2) with some clever triangulation of the polygons. Nicholas