[R-sig-Geo] FW: [STATSGRASS] Questions on calculating minimum distance between polygons and map attributes after m.in.e00

[White.Denis at epamail.epa.gov]

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