0
$\begingroup$

Suppose we have a circular radar that scans for ships in an area enclosed by $x^2+y^2 \leq z^2$ (a circle).

We wish to design a hash function $h$ such that, we can order the $n$ ships from closest to furtest away from the origin.

We want to have an expected time complexity of this ordering algorithm to be done in $\theta(n)$ time.

Each ship has a coordinate $(x,y)$, and so I want my hash function to be something like $\text{h((x,y)) = small index if close to origin, big index if farther}$.

What would be a hash function and algorithm that can run in expected $\theta(n)$ time?

I think my hash function should be something like the following, taking into account the distance:

$h((x,y)) = \sqrt{(x-0)^2 + (y-0)^2} = \sqrt{x^2+y^2}$

$\endgroup$

bumped to the homepage by Community 14 hours ago

This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.

0
$\begingroup$

You can't. This problem is as hard as sorting, so it'll need $\Omega(n \log n)$ time (in the comparison-based model); it's not reasonable to expect a linear-time algorithm for sorting.

The obvious solution is to sort the points by their distance from the origin. If the hash function computes the distance from the origin, well, then you're just sorting hash values.

$\endgroup$
0
$\begingroup$

Hash functions should be constant. Ships move. As soon as a ship moves, whatever hash based data structure you are using is now invalid.

And you can’t use hash functions for sorting.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.