Zobrazeno 1 - 10
of 279
pro vyhledávání: '"Korman, Matias"'
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-har
Externí odkaz:
http://arxiv.org/abs/2404.10380
Autor:
Aichholzer, Oswin, Ballinger, Brad, Biedl, Therese, Damian, Mirela, Demaine, Erik D., Korman, Matias, Lubiw, Anna, Lynch, Jayson, Tkadlec, Josef, Uno, Yushi
For a set $P$ of $n$ points in the plane in general position, a non-crossing spanning tree is a spanning tree of the points where every edge is a straight-line segment between a pair of points and no two edges intersect except at a common endpoint. W
Externí odkaz:
http://arxiv.org/abs/2206.03879
Autor:
Abel, Zachary, Akitaya, Hugo, Chiu, Man-Kwun, Demaine, Erik D., Demaine, Martin L., Hesterberg, Adam, Korman, Matias, Lynch, Jayson, van Renssen, André, Roeloffzen, Marcel
We study Snipperclips, a computer puzzle game whose objective is to create a target shape with two tools. The tools start as constant-complexity shapes, and each tool can snip (i.e., subtract its current shape from) the other tool. We study the compu
Externí odkaz:
http://arxiv.org/abs/2105.08305
Autor:
Akitaya, Hugo A., Demaine, Erik D., Korman, Matias, Kostitsyna, Irina, Parada, Irene, Sonke, Willem, Speckmann, Bettina, Uehara, Ryuhei, Wulms, Jules
A well-established theoretical model for modular robots in two dimensions are edge-connected configurations of square modules, which can reconfigure through so-called sliding moves. Dumitrescu and Pach [Graphs and Combinatorics, 2006] proved that it
Externí odkaz:
http://arxiv.org/abs/2105.07997
Autor:
Conroy, Jonathan, Thierauf, Christopher, Rule, Parker, Krause, Evan, Akitaya, Hugo, Gonczi, Andrei, Korman, Matias, Scheutz, Matthias
Regular irradiation of indoor environments with ultraviolet C (UVC) light has become a regular task for many indoor settings as a result of COVID-19, but current robotic systems attempting to automate it suffer from high costs and inefficient irradia
Externí odkaz:
http://arxiv.org/abs/2104.02913
Autor:
Aichholzer, Oswin, Demaine, Erik D., Korman, Matias, Lynch, Jayson, Lubiw, Anna, Masárová, Zuzana, Rudoy, Mikhail, Williams, Virginia Vassilevska, Wein, Nicole
Given a graph where every vertex has exactly one labeled token, how can we most quickly execute a given permutation on the tokens? In (sequential) token swapping, the goal is to use the shortest possible sequence of swaps, each of which exchanges the
Externí odkaz:
http://arxiv.org/abs/2103.06707
Autor:
Horiyama, Takashi, Klute, Fabian, Korman, Matias, Parada, Irene, Uehara, Ryuhei, Yamanaka, Katsuhisa
We introduce a computational origami problem which we call the segment folding problem: given a set of $n$ line-segments in the plane the aim is to make creases along all segments in the minimum number of folding steps. Note that a folding might alte
Externí odkaz:
http://arxiv.org/abs/2012.11062
Autor:
Akitaya, Hugo A., Demaine, Erik D., Gonczi, Andrei, Hendrickson, Dylan H., Hesterberg, Adam, Korman, Matias, Korten, Oliver, Lynch, Jayson, Parada, Irene, Sacristán, Vera
We give both efficient algorithms and hardness results for reconfiguring between two connected configurations of modules in the hexagonal grid. The reconfiguration moves that we consider are "pivots", where a hexagonal module rotates around a vertex
Externí odkaz:
http://arxiv.org/abs/2012.07556
Motivated by applications in gerrymandering detection, we study a reconfiguration problem on connected partitions of a connected graph $G$. A partition of $V(G)$ is \emph{connected} if every part induces a connected subgraph. In many applications, it
Externí odkaz:
http://arxiv.org/abs/2011.07378
Autor:
Chiu, Man-Kwun, Demaine, Erik D., Diomidova, Jenny, Eppstein, David, Hearn, Robert A., Hesterberg, Adam, Korman, Matias, Parada, Irene, Rudoy, Mikhail
Given a set of point sites, a sona drawing is a single closed curve, disjoint from the sites and intersecting itself only in simple crossings, so that each bounded region of its complement contains exactly one of the sites. We prove that it is NP-har
Externí odkaz:
http://arxiv.org/abs/2007.15784