nearest 2 neighbors?

Article View: comp.lang.c++.leda

Article #66

Back to comp.lang.c++.leda Previous Next

#66

From: William Hunter Hudson
Date: Tue, 05 Sep 1995 20:11

20 lines
1223 bytes

Is there a better way to find the nearest 2 neighbors in LEDA
than using 2 calls to S.nearest_neighbor?  Example:

p = point(x,y);
// nearest:   nearest point to p
// 2nd_nearest:   2nd nearest point to p

ps_item nearest = S.nearest_neighbor(q);       // O(n^2)
S.change_inf(nearest, far_away);               // O(1)
ps_item 2nd_nearest = S.nearest_neighbor(q);   // O(n^2)
S.change_inf(nearest, back_to_original);       // O(1)

----------------------------------------------------
Wm. Hunter Hudson    hunter@george.ee.washington.edu
Univ. of Washington; Dept. of Electrical Engineering
211 EEB; Box 352500; Seattle, WA 98195-2500
http://george.ee.washington.edu/~hunter
EEB lab    (206) 543-2505    WTC lab  (206) 685-7629
EEB office (206) 543-1245    FAX dept (206) 543-3842
----------------------------------------------------

Technical Details

Message-ID: <42iau2$11p@nntp5.u.washington.edu>

Path: arc1-ca.pugleaf.net!george.ee.washington.edu!hunter

Show Full Headers

Complete Article Headers

Path: arc1-ca.pugleaf.net!george.ee.washington.edu!hunter
From: hunter@george.ee.washington.edu (William Hunter Hudson)
Newsgroups: comp.lang.c++.leda
Subject: nearest 2 neighbors?
Date: 5 Sep 1995 20:11:46 GMT
Organization: Intelligent Systems Lab., Univ. of Washington
Distribution: world
Message-ID: <42iau2$11p@nntp5.u.washington.edu>
NNTP-Posting-Host: ra.ee.washington.edu