Proximity-constrained siting
Walk down a commercial street in NYC, and you will likely see a diverse mixture of establishments lining the sidewalk. However they happened to pop up, your dinner spot might share a block with a laundromat, florist, or bakery. While this mix of uses is frequently organic, the city also identifies some establishment-types it would rather not have clustered. A block full of high-end clothing stores might give a neighborhood its special character. A block full of nothing but low-price liquor stores would give a neighborhood a very different special character. Occasionally, policy-makers decide some types of “character” should not exist in NYC, and use proximity restrictions to break up clusters of establishment-types.
For example, let’s say I strongly believe there are detrimental effects caused by clusters of donut shops — sprinkles littered on the sidewalks, sugar-high children, local residents’ diets ruined... These effects compound the more donut shops I have in a given area. To ameliorate this problem, I impose a restriction that no donut shop can exist within 500ft of another donut shop. This way, NYC donut-makers can theoretically still make a living, but a problematic cluster is broken up.
Proximity restrictions like this one are an interesting siting problem, whether theoretical or actual (as of yet, NYC does not have an Agency of Fried Confections opening city-run donut shops). Not every lot is “eligible” to have a donut shop. As soon as a lot gets a shop, all of the lots within a 500ft radius are no longer available for future shops. Given these restrictions, some placements of shops on lots will lead to a greater number of total possible donut shops than others.
When the locations of establishments on city lots have proximity restrictions, what is the greatest number of establishments we can legally fit within the city?
NYC Planning’s Data Engineering team was recently tasked with answering this question. We began with spatial data for city lots — a subset of the PLUTO dataset. Our first step was to buffer each of these lots to 500ft, creating data that looks like this:
These buffers can tell us whether any given pair of lots can both have an establishment on them. Let’s look at a simplified example:
If the buffer for a lot overlaps with another lot, then we cannot have establishments on both of them, because they are within 500ft of each other. In this case, we can have an establishment on block 1 or block 2, but not on both. That would lead to a cluster! We can represent this in a matrix.
If an establishment exists on lot 0, we cannot place an establishment on lot 1. They are too close. To represent this, we put a 0 in the 0,1 position of our matrix. We can, however, place an establishment on lot 2, so we place a 1 in the 0,2 position of the matrix. Using this matrix, we’ve transformed a complicated spatial problem with distance calculations in to simple zeros and ones.
We can use this matrix to efficiently calculate all of the possible arrangements of establishments amongst these lots. If you are interested in how this is done, keep reading!
Using the matrix to find all possible shop arrangements
The first step is to hypothetically assign an establishment to a lot. For simplicity, we will assign it to the first indexed lot, lot 0. Referring back to our matrix, we can know all of the lots that can also have an establishment. Look at the first row. This row tells us where we can put a new shop, given that there is already a shop on lot 0.
Remember, the “1s” mean there can be a shop placed on that lot. In this case, we can place a shop on lot 2 or lot 3. We cannot place a shop on lot 1, because it is too close. The “ — ” in the first slot shows that we already have a shop on lot 0.
Let’s place the next shop on lot 2. Take a look at our simple picture above. The buffer for lot 0 does not overlap with lot 2. This is a “legal” shop placement. Can we fit in any more shops?
This is where things get interesting. We can’t just make a decision based on distance from lot 2. We also have to account for lot 0, our initial shop. To do this, we can multiply all of the values in the 0 row of our matrix by the 2 row.
In this case, the only 1 left in the row is associated with lot 3. We can place a shop on lot 3. Can we squeeze in one more shop? The picture above should intuitively tell you “no.” But let’s check the matrix. We now have to make sure the next shop is far away from three existing shops. To represent this, we multiply rows 0, 2, and 3.
There are no ones. This means all of the other lots are either too close (have zeros), or already have shops on them (have -). So a possible arrangement of shops in the city is lots 0, 2, and 3 with a grand total of three possible lots.
What about the other arrangements?
Take a look back at the simple example we’re working with. We could have arranged shops differently. If we had instead started by placing a shop on lot 1, rather than lot 0, we would have found a different, equally legal arrangement. It would look like this:
Lots 1 and 3 are far enough away to both have shops. We can’t fit any more shops into this scenario, because both lots 0 and 2 are too close to an existing shop.
To make sure we find all possible arrangements of shops on lots, we repeat the matrix-based process we walked through above. Each time, we chose a different lot on which to place our first shop. Sometimes, this gives us the same group of lots, just identified in a different order. This isn’t really a new solution, so we treat these as a single arrangement.
From here, we can take inventory of all of the possible arrangements of shops.
The best-case scenario
If you’re someone who really likes donuts (and likes having a variety of places to buy them), the second solution is not the optimal solution. Given this arrangement, the maximum possible shops is two. We call this the worst-case scenario. As it turns out, our first example was the best-case scenario, with a total of three lots that could be the future home of a shop.
Not only do we know how many shops could exist in the best-possible scenario, we also know how many ways there are obtaining that best-case scenario. We can even go back to the spatial data, PLUTO, and make a map of each arrangement!
If you’d like to dig into the code, you can find our algorithm in this repo.
