Efficient Amortized Time Algorithm

I have a data file containing all the cities in the United States and

their locations in latitute and longitute. I'm trying to develop a

Java application that takes in a latitute and longitute and returns

the nearest city. The easiest way to implement this is to compute the

distance between the input point and every city in the database. But

this is too inefficient, since its run-time would be O(n) for every

input entered (n is the number of items in the database). Is there a

way to sort the cities beforehand so that its run-time would be less

than O(n) once the user begins to give input?

Since this project has no practical purpose (just something I'd like

to accomplish during the summer), I do not care how inefficient it is

in sorting the data before the user enters inputs. The algorithm must

be more efficient that O(n) once the user enters inputs, though.

This solution should be understandable to a computer science student

who has just finished his first year. If it involves computational

geometry, please make sure that a layman can understand it. Since I

will be implementing this myself, I do not want referrals to programs

"out there" that already does this.

Clarification of Question bysecret901-ga

I meant that the easiest way to implement this is to compute the

distances between the input point and every city in the database and

then return the minimum.

Clarification of Question bysecret901-ga

IF your answer involves computational geometry, please explain it in

layman's terms. Voroni diagrams sounds like what I'm looking for, but

I don't understand it since I have no knowledge in computational

geometry. Please describe the algorithm, not just vaguely referencing


Clarification of Question bysecret901-ga

As hedgie and my question pointed out, this can be done in O(n).

However, the purpose of my project is not to make a practical

algorithm, but a "theoretically efficient" algorithm. So, although it

might be overkill, I still do want to go ahead with the project.

Note: for the purpose of this algorithm, one can assume that we're

working with a 2-dimensional plane instead of a surface of a sphere

since the cities are clustered so close together that the curvature of

the earth would not make much of a difference.

Leave a Reply

Your email address will not be published. Required fields are marked *