4 ms·
Is the equivalent problem in 3D harder or easier? Seems like it would be harder but you never know with these things.
by modeless 10mo ago
Is the equivalent problem in 3D harder or easier? Seems like it would be harder but you never know with these things.
- shermantanktop 10mo agoMy intuition says that with vertical walls, the problem collapses to 2d, but that 2d is a cross section of a 3d shape, and an infinite number of 3d shapes can hold that as the max cross section envelope.
- avadodin 10mo agoAs in a hyper-sofa moving around arbitrary unit hyper-square corners? The volume has to be greater than 1 unit in order to be a solution so it could be harder in higher dimensions.
- gcanyon 10mo agoI think it depends on what you mean by "equivalent" 1. If the walls are vertical and you are maximizing the horizontal area of the sofa and you are not allowed to reorient the sofa, then the problem collapses to the 2D case and the solution is the same. 2. If you are allowed to reorient the sofa while moving it, and the sofa doesn't have a minimum height, and the ceiling is arbitrarily high, then the sofa can be arbitrarily large by angling it to an arbitrary degree and then setting it flat for measuring. 3. So the in between case is where the ceiling is of some limited height and/or the sofa is of some arbitrary height, and then you have to decide whether the sofa has to be an extrusion of a 2D shape, or if it can be an arbitrary shape, at which point you're maximizing volume rather than area. And for that the obvious lower bound is the 2D maximum shape * the ceiling height. But maybe there's better?
- hugh-avherald 10mo agoWhat if you to traverse a tunnel that turns 90° in both the x and y directions?
- gcanyon 10mo agoI'm not sure what you mean by this?
- msephton 10mo agoA screw thread type thing?
- pastage 10mo agoI have not read the sofa problem I am not qualified to even talk about it. Given a rectangle tunnel, twist it so the walls become the ceiling, and also turn it in the same time. Seems like the same problem.. What is solved here is maximum shape, it feels like moving a object like this in 3D is basically a robot planning thing which in it self obviously magic for me. Finding a continuous path in a configuration space is the easy part, but then you have to understand how that changes when your shape changes.
- VorpalWay 9mo agoMy natural interpretation of "equivalent" would be a 1 wide, 1 tall corridor, and the goal is to maximise the volume instead of the area.
- layer8 9mo agoIt seems pretty obvious that the 2D solution is still optimal in that case, by making the sofa maximally tall (1) at all points. Though I don’t know if it has been proven yet.
- VorpalWay 9mo agoThat does seem like a reasonable guess, yet it was only in 1992 that the current (now proven optimal) solution to the 2D case was proven so. You could make the 3D case more interesting by having two corners: one in the plane and one out of the plane. It seems to me that that would need a new solution.
- layer8 9mo agoCertainly, and so would a 2D solution that has to support both left and right turns. To make 3D relevant for a single turn, one of the hallways could be rotated 45° lengthwise.
- murkle 9mo agoGoogle have just released a numerical solution to that one! https://colab.research.google.com/github/google-deepmind/alphaevolve_repository_of_problems/blob/main/experiments/the_3d_moving_sofa/the_3d_moving_sofa.ipynb#scrollTo=hHlwCsS-B3U- https://colab.research.google.com/github/google-deepmind/alp...