I have a point with coordinates x and y. I want to know all the points in a square around this point, with side L. For this, in postgresql/PostGIS, I use:

SELECT * FROM table_of_points WHERE (ST_Transform(the_geom,srid) && ST_MakeEnvelope(" + str(x-L) + ", " + str(y-L) + ", " + str(x+L) + ", " + str(y+L) + ", srid )

with srid being the Spatial Reference System Identifier.

What is the computational complexity of this query in PostGIS?

  • 1
    As a side note, another way to build a box around a point is to use ST_Expand, e.g.: ST_Expand(ST_SetSRID(ST_MakePoint(x, y), SRID), L)
    – Mike T
    Nov 29 '13 at 21:43
  • 1
    And in general, Mike's solution, avoiding string manipulations, is the preferred one. Nov 30 '13 at 3:45

If you have a spatial index built, it should be O(log(n))

  • 2
    If "n" refers to the number of points in the table, this answer cannot be correct in general, because it is possible for such a query to return all the points, which is a O(n) operation.
    – whuber
    Nov 29 '13 at 20:50
  • 1
    No, it refers to searching out one needle in the haystack, which I think is the usual question regards indexes, no? Nov 30 '13 at 3:44
  • I have a spatial index built. If n refers to the number of points in the table, @whuber has a point in my opinion. On the other hand, if we imagine that the total map of points is huge and that we look in a small square inside this map, with a spatial index built, wouldn't it be possible to express the complexity in terms of the mean density of points in the small square? (let's call it "d", the expected number of points in the square). In my example, d is not constant of course, but it stays in the same order of magnitude. So, O(log(d))?
    – Antonin
    Nov 30 '13 at 11:03
  • 1
    @Antonin Typically such searches take O(dlog(n)) computation: O(log(n)) for each of *d points. In certain circumstances, with certain data structures, the timing might be reducible to O(log(n) + d).
    – whuber
    Nov 30 '13 at 17:29

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.