There are some arbitrary-chosen points in 1D space. What needs to be found is the approximate number of them without counting all of them. It is possible to choose some coordinates (numbers) and for each one there are two numbers returned - the distances to the closest points to the left and to the right.

I'm looking for some sources on how to solve such problem efficiently so any papers, generalizations or similar problems are needed.

  • 1
    $\begingroup$ (1) Do we know any bounds on the region in which points may occur? Is the number of bits in the representation of the point coordinates allowed as a variable in runtime analysis? (2) Are randomized algorithms acceptable? (3) While this problem seems quite interesting, you might want to make the question a bit more specific as at the moment it risks being closed for being too broad (especially with the last sentence). $\endgroup$ – Aaron Rotenberg Dec 29 '19 at 3:44
  • $\begingroup$ If we don't know any bounds on the size of the point coordinates, then the points may be arbitrarily far from the origin or arbitrarily close together and the distance oracle may take superpolynomial time to query exactly. On the other hand, if we have a polynomial bound on the number of bits of the point coordinates as binary fractions, then we might as well assume they are all integer coordinates since we can multiply everything by a power of 2 common denominator. $\endgroup$ – Aaron Rotenberg Dec 29 '19 at 4:11

Your Answer

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

Browse other questions tagged or ask your own question.