Zobrazeno 1 - 10
of 138
pro vyhledávání: '"Lynch, Jayson"'
Autor:
MIT CompGeom Group, Akitaya, Hugo A., Demaine, Erik D., Hesterberg, Adam, Lubiw, Anna, Lynch, Jayson, O'Rourke, Joseph, Stock, Frederick, Tkadlec, Josef
A polyiamond is a polygon composed of unit equilateral triangles, and a generalized deltahedron is a convex polyhedron whose every face is a convex polyiamond. We study a variant where one face may be an exception. For a convex polygon P, if there is
Externí odkaz:
http://arxiv.org/abs/2408.04687
Autor:
MIT CompGeom Group, Akitaya, Hugo A., Demaine, Erik D., Hesterberg, Adam, Lubiw, Anna, Lynch, Jayson, O'Rourke, Joseph, Stock, Frederick
We explore an Art Gallery variant where each point of a polygon must be seen by k guards, and guards cannot see through other guards. Surprisingly, even covering convex polygons under this variant is not straightforward. For example, covering every p
Externí odkaz:
http://arxiv.org/abs/2404.04613
Autor:
MIT CompGeom Group, Abel, Zachary, Akitaya, Hugo A., Demaine, Erik D., Hesterberg, Adam C., Lynch, Jayson
This paper characterizes when an $m \times n$ rectangle, where $m$ and $n$ are integers, can be tiled (exactly packed) by squares where each has an integer side length of at least 2. In particular, we prove that tiling is always possible when both $m
Externí odkaz:
http://arxiv.org/abs/2308.15317
Autor:
Ani, Hayashi, Coulombe, Michael, Demaine, Erik D., Diomidova, Jenny, Gomez, Timothy, Hendrickson, Dylan, Lynch, Jayson
We extend the motion-planning-through-gadgets framework to several new scenarios involving various numbers of robots/agents, and analyze the complexity of the resulting motion-planning problems. While past work considers just one robot or one robot p
Externí odkaz:
http://arxiv.org/abs/2306.01193
Autor:
Alaniz, Robert M., Brunner, Josh, Coulombe, Michael, Demaine, Erik D., Diomidova, Jenny, Knobel, Ryan, Gomez, Timothy, Grizzell, Elise, Lynch, Jayson, Rodriguez, Andrew, Schweller, Robert, Wylie, Tim
We analyze the computational complexity of basic reconfiguration problems for the recently introduced surface Chemical Reaction Networks (sCRNs), where ordered pairs of adjacent species nondeterministically transform into a different ordered pair of
Externí odkaz:
http://arxiv.org/abs/2303.15556
Autor:
Brunner, Josh, Chung, Lily, Coulombe, Michael, Demaine, Erik D., Gomez, Timothy, Lynch, Jayson
We analyze Solo Chess puzzles, where the input is an $n \times n$ board containing some standard Chess pieces of the same color, and the goal is to make a sequence of capture moves to reduce down to a single piece. Prior work analyzes this puzzle for
Externí odkaz:
http://arxiv.org/abs/2302.01405
Autor:
Adler, Aviv, Ani, Hayashi, Chung, Lily, Coulombe, Michael, Demaine, Erik D., Diomidova, Jenny, Hendrickson, Dylan, Lynch, Jayson
We analyze the puzzle video game This Game Is Not Going To Load Itself, where the player routes data packets of three different colors from given sources to given sinks of the correct color. Given the sources, sinks, and some previously placed arrow
Externí odkaz:
http://arxiv.org/abs/2302.01145
Planar/flat configurations of fixed-angle chains and trees are well studied in the context of polymer science, molecular biology, and puzzles. In this paper, we focus on a simple type of fixed-angle linkage: every edge has unit length (equilateral),
Externí odkaz:
http://arxiv.org/abs/2212.12450
We prove essentially optimal fine-grained lower bounds on the gap between a data structure and a partially retroactive version of the same data structure. Precisely, assuming any one of three standard conjectures, we describe a problem that has a dat
Externí odkaz:
http://arxiv.org/abs/2211.14664
Autor:
Coulombe, Michael, Lynch, Jayson
Publikováno v:
EPTCS 370, 2022, pp. 213-228
In this paper we define a new model of limited communication for multiplayer team games of imperfect information. We prove that the Team DFA Game and Team Formula Game, which have bounded state, remain undecidable when players have a rate of communic
Externí odkaz:
http://arxiv.org/abs/2209.10324