nearest 2 neighbors?

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

2 messages

[T] Back to Threads [V] Tree View [G] Group Articles

2 total messages Started by William Hunter Hudson Tue, 05 Sep 1995 20:11

#66

Author: 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
----------------------------------------------------

Re: nearest 2 neighbors?

#67

Author: Wolfram Schlickenrieder (KSC)
Date: Tue, 05 Sep 1995 23:25

25 lines
1339 bytes

hunter@george.ee.washington.edu (William Hunter Hudson) writes:

> 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)


If computing distances is no too expensive -- what do you
think of: 

compute distances ;             // O(n)
sort them in descending order ; // O(n log n)
take the first 2;        	// O(1)

?
Wolf

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads