As a former architect, it's tempting to see similarities in the way architects do space planning: continually re-arranging the various rooms/circulation elements to find the most efficient use of space. Seeing how counter-intuitive these solutions are (and the fact that most of them are not proved, only "found") makes me think that space-planning may not be "solvable" computationally.
> space-planning may not be "solvable" computationally
It isn't. The knapsack problem is NP-complete and roughly translates to "Given a space of size X and a set of items of sizes A, B, C, how do you pack X optimally?". Designing a room layout seems like it would fall squarely into that, with additional restrictions added on top to make it even harder.
I mean, NP-complete problems are perfectly solvable computationally, and given the relatively small number of rooms per floor that architects are concerned with, finding the optimal solution with a computer should still take much less time than it takes a human to come up with some local optimum in the design space. The real problem is actually encoding all the constraints that an architect is really working under, including such inherently difficult-to-quantify aspects as aesthetics, ergonomics, and familiarity! A solution that maximizes the available m^2 is useless if its human users find it too weird.
The knapsack solution space is countable and effectively finite, and thus is solvable, even if not efficiently due to NP-completeness. Space-planning has to work with a potentially uncountable number of positions/orientations in continuous space, and thus might be different.
This made me scratch my head a bit. I'm aware of there being different types of infinities, but to call a "smaller" infinity "effectively finite" seems a bit odd. I'm not up-to-date on math terminology, though.
In truth, I'm not quite sure what you mean by "solvable" vs "not solvable" here, either. In the above discussion I thought it meant "not tractable in a reasonable amount of time" (i.e. NP-complete => "not solvable"). But you seem to have a different definition you're working from.
Could you elaborate on what you mean by "effectively finite => solvable" ?
It is effectively finite in that the knapsack has a finite capacity and there is a finite selection of items with positive weight, hence the number of items that can fit into the knapsack is limited by the knapsack capacity divided by the smallest item weight. So, while for the unbounded knapsack problem the number of instances of an item that may be included is not limited, it is effectively still limited by the knapsack capacity. Therefore the number of item combinations that have to be considered is finite as well.
The GP had put "solvable" in quotes. I understood the GP to say that for space planning, there may not be an algorithm that is guaranteed to produce an answer in finite time. For the knapsack problem there is such an algorithm (even if that finite time, due to NP-completeness, could be very long).
The knapsack problem has a finite number of solutions. You can brute-force the optimal solution, if you don't care about efficiency. Ditto the Traveling Salesman problem.
I'm not sure whether this problem is finite or not, given that you can place objects at any real-number coordinates and any real-number angle. But if you simply make those increments small enough (you can only put boxes a whole number of planck-lengths apart) then there are a finite number of possible arrangements, so it's possible to brute-force.
I saw it as well and immediately I thought of posting it here, but as always I search before I post and it was reposted a year ago, so I decided not to.
Glad you did post it though because it’s a really nice visualization and a very good page and deserves to be seen by more people who like such things!
As a former architect, it's tempting to see similarities in the way architects do space planning: continually re-arranging the various rooms/circulation elements to find the most efficient use of space. Seeing how counter-intuitive these solutions are (and the fact that most of them are not proved, only "found") makes me think that space-planning may not be "solvable" computationally.