25 citations · 112 across the 30 of their papers we have counts for
6 papers · 1 filter
Rendezvous of two robots with visible bits
Giovanni Viglietta
We study the rendezvous problem for two robots moving in the plane (or on a line). Robots are autonomous, anonymous, oblivious, and carry colored lights that are visible to both. W…
Guarding and Searching Polyhedra
Giovanni Viglietta
We tackle the Art Gallery Problem and the Searchlight Scheduling Problem in 3-dimensional polyhedral environments, putting special emphasis on edge guards and orthogonal polyhedra.
Classic Nintendo Games are (Computationally) Hard
Greg Aloupis, Erik D. Demaine, Alan Guo +1
We prove NP-hardness results for five of Nintendo's largest video game franchises: Mario, Donkey Kong, Legend of Zelda, Metroid, and Pokemon. Our results apply to generalized versi…
Lemmings is PSPACE-complete
Giovanni Viglietta
Lemmings is a computer puzzle game developed by DMA Design and published by Psygnosis in 1991, in which the player has to guide a tribe of lemming creatures to safety through a haz…
Gaming is a hard job, but someone has to do it!
Giovanni Viglietta
We establish some general schemes relating the computational complexity of a video game to the presence of certain common elements or mechanics, such as destroyable paths, collecti…
Partial Searchlight Scheduling is Strongly PSPACE-Complete
Giovanni Viglietta
The problem of searching a polygonal region for an unpredictably moving intruder by a set of stationary guards, each carrying an orientable laser, is known as the Searchlight Sched…