[HN Gopher] Squares in Squares
___________________________________________________________________
Squares in Squares
Author : yowzadave
Score : 132 points
Date : 2023-02-15 19:13 UTC (3 hours ago)
(HTM) web link (erich-friedman.github.io)
(TXT) w3m dump (erich-friedman.github.io)
| Recursing wrote:
| Other fun packings: https://erich-friedman.github.io/packing/
|
| I particularly liked "squares in circles", found 8 pretty
| surprising
| fabledAble wrote:
| It reminds me of a real life "problem" I like to solve around the
| holidays: what is the smallest cut of wrapping paper required to
| wrap a given box. With a restriction in one dimension. I find
| that, most of the time for cube-ish boxes, using a somewhat
| diagonal orientation can result in a shorter cut of wrapping
| paper used, and reduces the amount of tape needed to keep it on
| the shape as well!
| bee_rider wrote:
| My mom did upholstery as a hobby; it only occurred to me in
| adulthood that wrapping paper isn't designed so that the
| patterns would just magically line up somehow.
| layer8 wrote:
| I'd like to read a systematic analysis of that.
| sitkack wrote:
| If you are fond of these geometric constructions you might like
| the artist https://www.artsy.net/artist/victor-vasarely
| mzs wrote:
| I can recommend the museum as well:
| https://en.vasarely.hu/vasarelys-periods/
| gerikson wrote:
| Really fun and counterintuitive arrangements.
|
| The linked paper has more details
|
| https://erich-friedman.github.io/papers/squares/squares.html
| BeefySwain wrote:
| I'd like to see the percentage improvement over the "naive"
| approach (just stacking them edge-to-edge) for each of them. I
| can't tell if the improvements are significant enough for this to
| have obviously practical benefits.
| layer8 wrote:
| Obviously(?) the improvement decreases with increasing n. From
| the table in [0], regarding the length (not area) of the
| square, it is about 10% for n=5 and 7.5% for n=10, and 4.6% for
| n=82.
|
| [0] https://erich-
| friedman.github.io/papers/squares/squares.html...
| yowzadave wrote:
| Originally saw this in a twitter thread by Daniel Piker:
| https://twitter.com/kangaroophysics/status/16254239511563755...
|
| 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.
| Swizec wrote:
| > 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.
|
| https://en.wikipedia.org/wiki/Knapsack_problem
|
| According to wikipedia we do have algorithms that are useful in
| practice, but that's not quite the same as "definitely optimal"
| Sharlin wrote:
| 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.
| layer8 wrote:
| 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.
| turtledragonfly wrote:
| > effectively finite
|
| 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" ?
| NKosmatos wrote:
| 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!
___________________________________________________________________
(page generated 2023-02-15 23:00 UTC)