2

I'm not sure if I've been searching using the wrong keywords, but I've tried so many different ways of wording this and I can't find a relevant answer.

Basically, given a set of circles defined by their centers and radii and a point (x, y), I want to find all circles whose radii cover that particular point.

For example, say I have a website that lists a bunch of delivery restaurants that deliver only as far as a certain radius from their restaurant. I live at (x, y) and I want to run a query in my database that finds all the restaurants that deliver food to my place, so even if a restaurant is in Tokyo and if it claims to deliver within a radius of one light year, it should show up in a Californian's search.

The naive way is just to loop through all restraints in the database and compare the distance and the radius. How is this any different in terms of efficiency from a query that searches for all restaurants lying within a defined circle (typical Yelp problem)?

  • 1
    Define "better". If you have to run such a query just once, you at least have to read the data of each restaurant once, so running time cannot be better than O(N) where N is the number of restaurants. Or do you want to run such queries very often (for example, many millions of times) with a fixed set of restaurants? Your current wording gives no indication of this. – Doc Brown Jun 14 '15 at 5:46
  • I want to run this kind of queries very often. Is O(n) really the best we can do here? I was hoping there would be some kind of database optimization. Because on the other hand, the conventional Yelp problem of finding all restaurants lying within x miles of a point is high school math. So the question is: does a database query really look at all points and does this comparison operation on every single one of them? Because in that case, my problem and the conventional Yelp searching problem would be equally efficient/inefficient, right? – Dovizu Jun 14 '15 at 5:55
  • 1
    Give readers a favor and edit your question, adding the missing information to your question text instead of burying it down here in the comments. Now you mention "multiple queries", you mentioned a database, all these things you should have written above in the question in the first place. – Doc Brown Jun 14 '15 at 6:05
  • Edited it, could you reconsider answering this question? – Dovizu Jun 14 '15 at 6:12
3

I was hoping there would be some kind of database optimization

Databases with spatial / geospatial extensions allow to store spatial objects and fast query operations like "is point in certain area", supported by so-called spatial indexes. The exact set of features as well as the syntax differs from DBMS to DBMS, but I do not know of a database which supports circle objects of different radius directly. But if your spatial database supports polygons (which is pretty standard), you can utilize this for your problem:

  • for each circle, store (additionally to center and radius) a polygon which encloses the circle (for lots of practical purposes, the enclosing square is good enough).

  • use a spatial query for getting all circles where your given point (x,y) is contained in the related square. If you have many circles in total in your database, this could reduce the number of circles for a the point (x,y) to a much smaller amount

  • for the (hopefully small) result set, you test the "inside circle" condition manually by looping through the circles

In fact, you have to check if you benefit from this optimization in combination with your real data, and if the additional overhead of storing the enclosing polygons is really worth the hassle.

|improve this answer|||||
0

You want to find things in a two-dimensional space easily. That is similar to the more common problem of finding things in a one-dimensional space; the solution there is to sort your data and then find things in it in O(log n) time via binary search.

You can't do exactly the same thing for two-dimensional data because the ordering is not the same for the two dimensions (a point that is quite small by one dimension might be very large by the other). But there are many generalizations of sorting/indexing that will nevertheless save you a lot of time in practice. The question has already been asked on stackoverflow, here.

|improve this answer|||||
0

Databases has special index type for such kind of searches based on Minimum Bounding Boxes, called r-tree. Let's assume that we have 1M places defined by x/y in our database and we want to find all points in radius from our position we first need to build MBR containing search circle (center point in this same place and edges 2r), search data and in next step throw away results placed in MBR corners using simple formula x*x+y*y < r*r. R-tree aka range tree has also many of in-memory implementations for different languages. If you want to solve geographical problem it would be a little bit more complex as we have meridian, date change line and more complicated distance calculations (great circle).

|improve this answer|||||
  • I see. So if instead I were to execute a query that look for all circles which cover a particular point, it will be a lot more inefficient because you can't use an MBB to narrow down the search, is that correct? – Dovizu Jun 14 '15 at 21:39
  • Yes r-tree seeking is O(log2(n)) looping is O(n), so simply it's better to reverse order - first find potential results with r-tree then filter them up with geometry/geodetic calculations. – piotrpo Jun 16 '15 at 7:24

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.