4 ms·

What would be an efficient solver for this problem, and what would the running time be? Seems like a naive solver would be too slow for this, could it be restat

What would be an efficient solver for this problem, and what would the running time be? Seems like a naive solver would be too slow for this, could it be restated into finding the minimal number of cuts needed to fully disconnect a planar graph?

klmadfejno 6y ago
My gut intuition says you don't need to check the entire space of possible lines, just the lines between any two dots (rotated by an trivially small degree to separate the two), because a "correct" cut should always be defined by the bounds between which some dot on the border is included or excluded in a given cut. You also don't need to check each sequence of legal cuts. Most positions can be deduced to be unwinnable given n-remaining moves.
- eutectic 6y ago
  I came up with basically this same idea independently when writing my solver (pasted in my top-level comment). It mostly works well, but it isn't obvious how to extend it to capture non-convex geometry. E.g. cutting off 2 ears to create 3 regions vs cutting off whole head to create 2 regions.
  - klmadfejno 6y ago
    That's an impressive quick effort. My second initial gut reaction says you could add a point to the graph at the local minima of a non-convex curve and use it as a way to generate additional candidate, but not require the solver to eliminate it? Could probably smoosh an extra rule inn there somehow to eliminate pieces on that particular piece, but it wouldn't generalize to all non convex curves.
    - eutectic 6y ago
      After some thought I think it works as-is if you just delete all edges between points which can't directly see each-other, as long as the visibility graphs are still connected. The best cuts could then sometimes be edge->edge instead of always vertex->vertex. (e.g. each point at a random position in a little bump, where you want to slice off all the bumps in one go without going off at a random angle. I'm trying to think about the topology of cuts in the plane but its hard to visualize. I guess it must be related to Voronoi and Delaunay.

klmadfejno 6y ago

My gut intuition says you don't need to check the entire space of possible lines, just the lines between any two dots (rotated by an trivially small degree to separate the two), because a "correct" cut should always be defined by the bounds between which some dot on the border is included or excluded in a given cut. You also don't need to check each sequence of legal cuts. Most positions can be deduced to be unwinnable given n-remaining moves.

eutectic 6y ago
I came up with basically this same idea independently when writing my solver (pasted in my top-level comment). It mostly works well, but it isn't obvious how to extend it to capture non-convex geometry. E.g. cutting off 2 ears to create 3 regions vs cutting off whole head to create 2 regions.
- klmadfejno 6y ago
  That's an impressive quick effort. My second initial gut reaction says you could add a point to the graph at the local minima of a non-convex curve and use it as a way to generate additional candidate, but not require the solver to eliminate it? Could probably smoosh an extra rule inn there somehow to eliminate pieces on that particular piece, but it wouldn't generalize to all non convex curves.
  - eutectic 6y ago
    After some thought I think it works as-is if you just delete all edges between points which can't directly see each-other, as long as the visibility graphs are still connected. The best cuts could then sometimes be edge->edge instead of always vertex->vertex. (e.g. each point at a random position in a little bump, where you want to slice off all the bumps in one go without going off at a random angle. I'm trying to think about the topology of cuts in the plane but its hard to visualize. I guess it must be related to Voronoi and Delaunay.