Show Bid Request
Date Structures (Generating Points)
Bid Request Id: 32091
|
|
|
|
Posted by: |
seatiger74 (25 ratings)
(Software buyer rating 10 )
|
|
Non-action Ratio: |
Very Good - 3.23%
|
Buyer Security Verifications: |
Good
|
|
Approved on: |
Oct 22, 2002
10:21:48 PM EDT
|
|
Bidding Closes: |
Oct 31, 2002
10:33:06 PM EDT
|
|
Viewed (by coders): |
178 times
|
|
Deadline: |
11/2/2002
TIME EXPIRED
|
|
|
|
|
Description:
Consider the problem of finding the two points that are closest together among a set of points. It would seem that one must examine the distances between all pairs of points in the set, which would mean a runtime
proportional to N2. However, it turns out that we can use sorting to get by with examining only about N log(N) distances between points in the worst case (and far fewer on average).
The idea is to sort the points on one coordinate, say x, then use that ordering to divide the points in half. Then the closest pair in the whole set is either the closest pair in one of the halves or the
closest pair with one member in each half. How we handle the latter case is what makes this code interesting (and what makes it more -- or less --
efficient).In looking at the points on either side of the dividing line between the 2 halves, we need only look at those that are within distance min of the dividing line, where min is the smaller of the distances between the closest pairs found in the 2 halves.Unfortunately, there could be many such points. It would seem necessary to sort the points in this strip on y. After that, we can limit the number of distance computations involving each point as follows: proceeding through the points in increasing y order, check if each point is inside the vertical strip containing all points in the plane within min of the dividing line. For each such point, compute the distance between it and any point in the
strip whose y-coordinate is less than the y-coordinate of the current point,but not more than min less. The fact that the distance between all pairs of points in each half is at least min means that only a few points are likely to be checked.The above approach can be shown in the worst case to have a running time of N log2N. To actually get an N log N worst case, we must avoid the sort of y. The way to do this is not that complicated, but is subtle. Recall the mergesort routine. Make a merge sort that sorts a linked list (of points) on their y-coordinate -- but at the same time that it is sorting, have it find the closest pair.
Your assignment is to randomly generate a list of 100,000 points (with all the coordinates in the range from 0 to 1000) and find and print the closest
pair of points and their distance apart. You MUST use an algorithm that runs faster than N2; if you can do it in N log N, you can get 5 points extra credit. (continue next open window)
Deliverables:
1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done.
2) Installation package that will install the software (in ready-to-run condition) on the platform(s) specified in this bid request.
3) Complete ownership and distribution copyrights to all work purchased.
Platform:
(continue)
Compute and print the cpu time for how long your code takes to find the closest pair of points.
Please write this program in C++. I use Visual C++ 6.0 to run it
Must be 100% finished and received by buyer on:
Nov 2, 2002 EDT
Deadline legal notes: All times are expressed in the time zone of the site EDT (UT - 5). If the buyer omitted a time, then the deadline is 11:59:59 PM EDT on the indicated date.
Special Conditions / Other:
Please deliver codes ontime
Remember that contacting the other party outside of the site (by email, phone, etc.) on all business projects < $500 (before the buyer's money is escrowed) is a violation of both the software buyer and seller agreements.
We monitor all site activity for such violations and can instantly expel transgressers on the spot, so we thank you in advance for your cooperation.
If you notice a violation please help out the site and report it. Thanks for your help.
|
|
|
Bidding/Comments:
|
All monetary amounts on the site are in United States dollars.
Rent a Coder is a closed auction, so coders can only see their own bids and comments. Buyers can view every posting made on their bid requests. |
See all rejected bids (and all comments)
| Name |
Bid Amount
|
Date |
Coder Rating |
|
|
This bid was accepted by the buyer!
|
$15 (USD)
|
Oct 23, 2002
5:43:50 PM EDT
|
9.83
(Excellent)
|
|
|
Hi!
I'd like to do your project. It is quite simple and you will surely have it before the deadline.
It will be simple, clear and well explained. Trust me, I have experience in algorithms.
Yours,
Eugen
|
|
|
|
|
|
|