dist btwn points sbjct to threshold

[Frederic Cazals]

Dear All,

as a follow-up to the discussion regarding bucket-based strategies to
retrieve the pairs of points whose distance is less than a given
threshold, some variants of uniform grids deserve a quote. uniform
grids indeed solve the problem efficiently (theoretically and
practically) as long as the points' distribution is uniform. if not,
variants (in particular recursive grids) are a better choice. the
following bibliography discusses some of these issues:

@book{d-lnba-86
, author =      "L. Devroye"
, title =       "Lecture Notes on Bucket Algorithms"
, publisher =   "Birkh{\"a}user Verlag"
, address =     "Boston, MA"
, year =        1986
, keywords =    "book"
}

@inproceedings{cp-blspd-97
, author =      "F. Cazals and C. Puech"
, title =       "Bucket-like space partitioning data structures with applications to ra
y tracing"
, booktitle =   "Proc. 13th Annu. ACM Sympos. Comput. Geom."
, year =        1997
, pages =       "11--20"
, cites =       "a-fcagi-94, aeiim-pubtc-85, c-cpoda-97, cdp-fchcn-95, cs-sigte-97, bko
s-cge-95, d-lnba-86, d-mddtd-88, glm-othsr-96, jl-rrt-92, ks-frtua-97, bwy-oetac-80, mm
s-qsrs-94, nhs-gfasm-84, o-cgc-94, ps-cgi-85, s-iggp-76, s-igbmf-93, sd-fbcve-95, sd-cs
dta-95, w-ltsbv-92, ZZZ"
, update =      "98.07 bibrelex, 97.07 efrat"
}

@inproceedings{ho-smhsr-94
, author =      "D. Halperin and M. H. Overmars"
, title =       "Spheres, Molecules, and Hidden Surface Removal"
, booktitle =   "Proc. 10th Annu. ACM Sympos. Comput. Geom."
, year =        1994
, pages =       "113--122"
, cites =       "abbkw-pdb-87, bkwmbrkst-pdbcb-77, cegs-sessr-91, cegsw-ccbac-90, c-sas
pn-83, b-rsdoh-93, dkmmrt-dphul-88, fp-eagcs-93, fo-fdmm-, gs-pmgsc-85, s-hb-70, kos-eh
sro-92, klps-ujrcf-86, lr-ipses-71, mmpssw-ftdlm-91, m-ms-90, o-plfs-92, ps-cgi-85, s-a
tubl-93, sho-cfsrm-93, vb-facrs-93, ZZZ"
, update =      "98.03 bibrelex, 94.09 jones, 94.01 jones"
}

Frederic Cazals.


On Tue, Jul 10, 2001 at 09:19:04PM -0400, Paul Heckbert wrote:
> The algorithm you describe takes O(n^2) time, where n is the number of
> points, and that is of course the best you can do for arbitrary point sets,
> since the output set could be that large, but when you have fairly well
> distributed points, as you probably do for protein work, you should be able
> to get O(n) performance in practice.
> 
> A simple algorithm I've used for related problems is to create a k*k*k grid
> of cubes, each of which contains a list of points within it.  You could
> choose k such that your cube size is proportional to the threshold distance
> you're interested in, or if your points are uniformly distributed through
> space (probably not true for proteins) you could try k proportional to n^.33
> .  Using that simple data structure, it is a simple matter of checking a
> cube and perhaps some of the neighboring cubes to find all points within a
> given distance of some query point.  If your points are well-distributed and
> you've chosen k appropriately, the average work required for each query will
> be O(1), so finding all pairs with distance below threshold will be O(n).
> 
> See the paper "Fast Surface Particle Repulsion" at http://www.cs.cmu.edu/~ph
> for more details on the cubical bucketing scheme.
> 
> Paul Heckbert
> Computer Science Dept
> Carnegie Mellon University
-- 
------------------------------------ ---------------- -------- ---- -- -
-- Project PRISME, INRIA Sophia-Antipolis, 2004 route des Lucioles,
-- BP 93, F-06902 Sophia-Antipolis, 
-- Tel: 33 (0)4 92 38 71 88, Fax: 33 (0)4 92 38 76 43
-- Frederic.Cazals at sophia.inria.fr, http://www.inria.fr/prisme

-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.