MKMatias Korman

Matias Korman

*This is an algorithmically generated author record based on publicly available information.

Matias Korman has a total of 13 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Input-Sensitive Reconfiguration of Sliding Cubes

    by Hugo Akitaya, Matias Korman, Frederick Stock

    A configuration of $n$ unit-cube-shaped \textit{modules} (or \textit{robots}) is a lattice-aligned placement of the $n$ modules so that their union is face-connected. The reconfiguration problem aims at finding a sequence of moves that reconfigures the modules from one given configuration to another. The sliding cube model (in which modules are allowed to slide over the face or edge of neighboring modules) is one of the most studied theoretical models for modular robots. In the sliding cubes model we can reconfigure between any two shapes in $O(n^2)$ moves ([Abel \textit{et al.} SoCG 2024]). If we are interested in a reconfiguration algorithm into a \textit{compact configuration}, the number of moves can be reduced to the sum of coordinates of the input configuration (a number that ranges from $Ω(n^{4/3})$ to $O(n^2)$, [Kostitsyna \textit{et al.} SWAT 2024]). We introduce a new algorithm that combines both universal reconfiguration and an input-sensitive bound on the sum of coordinates of both configurations, with additional advantages, such as $O(1)$ amortized computation per move.

  • Open Access

    PSPACE-Hard 2D Super Mario Games: Thirteen Doors

    by MIT Hardness Group, Hayashi Ani, Erik D. Demaine, Holden Hall, Matias Korman

    We prove PSPACE-hardness for fifteen games in the Super Mario Bros. 2D platforming video game series. Previously, only the original Super Mario Bros. was known to be PSPACE-hard (FUN 2016), though several of the games we study were known to be NP-hard (FUN 2014). Our reductions build door gadgets with open, close, and traverse traversals, in each case using mechanics unique to the game. While some of our door constructions are similar to those from FUN 2016, those for Super Mario Bros. 2, Super Mario Land 2, Super Mario World 2, and the New Super Mario Bros. series are quite different; notably, the Super Mario Bros. 2 door is extremely difficult. Doors remain elusive for just two 2D Mario games (Super Mario Land and Super Mario Run); we prove that these games are at least NP-hard.

  • Open Access

    A Universal In-Place Reconfiguration Algorithm for Sliding Cube-Shaped Robots in a Quadratic Number of Moves

    by Zachary Abel, Hugo A. Akitaya, Scott Duke Kominers, Matias Korman, Frederick Stock

    In the modular robot reconfiguration problem, we are given $n$ cube-shaped modules (or robots) as well as two configurations, i.e., placements of the $n$ modules so that their union is face-connected. The goal is to find a sequence of moves that reconfigures the modules from one configuration to the other using "sliding moves," in which a module slides over the face or edge of a neighboring module, maintaining connectivity of the configuration at all times. For many years it has been known that certain module configurations in this model require at least $\Omega(n^2)$ moves to reconfigure between them. In this paper, we introduce the first universal reconfiguration algorithm -- i.e., we show that any $n$-module configuration can reconfigure itself into any specified $n$-module configuration using just sliding moves. Our algorithm achieves reconfiguration in $O(n^2)$ moves, making it asymptotically tight. We also present a variation that reconfigures in-place, it ensures that throughout the reconfiguration process, all modules, except for one, will be contained in the union of the bounding boxes of the start and end configuration.

  • Open Access

    Kinetic Geodesic Voronoi Diagrams in a Simple Polygon

    by Matias Korman, André van Renssen, Marcel Roeloffzen, Frank Staals

    We study the geodesic Voronoi diagram of a set $S$ of $n$ linearly moving sites inside a static simple polygon $P$ with $m$ vertices. We identify all events where the structure of the Voronoi diagram changes, bound the number of such events, and then develop a kinetic data structure (KDS) that maintains the geodesic Voronoi diagram as the sites move. To this end, we first analyze how often a single bisector, defined by two sites, or a single Voronoi center, defined by three sites, can change. For both these structures we prove that the number of such changes is at most $O(m^3)$, and that this is tight in the worst case. Moreover, we develop compact, responsive, local, and efficient kinetic data structures for both structures. Our data structures use linear space and process a worst-case optimal number of events. Our bisector and Voronoi center kinetic data structures handle each event in $O(\log^2 m)$ time. Both structures can be extended to efficiently support updating the movement of the sites as well. Using these data structures as building blocks we obtain a compact KDS for maintaining the full geodesic Voronoi diagram.