FW: [STATSGRASS] Questions on calculating minimum distance between polygons and map attributes after m.in.e00
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.
> I am not very familiar with the m.in.e00 command in GRASS. Is the
> to compute an all pairs min distance between all polygons in a set
> or just the min distance between two polygons or something inbetween.
> it is an all pairs problem then the optimum is O((n*m)^2) as Denis
> 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
> returned list from a range query with a bruteforce menthod. That may
> 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.