Greg Aloupis

TCS Journal 2015 Journal Article

Classic Nintendo games are (computationally) hard

• Greg Aloupis
• Erik D. Demaine
• Alan Guo
• Giovanni Viglietta

We prove NP-hardness results for five of Nintendo's largest video game franchises: Mario, Donkey Kong, Legend of Zelda, Metroid, and Pokémon. Our results apply to generalized versions of Super Mario Bros. 1–3, The Lost Levels, and Super Mario World; Donkey Kong Country 1–3; all Legend of Zelda games; all Metroid games; and all Pokémon role-playing games. In addition, we prove PSPACE-completeness of the Donkey Kong Country games and several Legend of Zelda games.

SODA Conference 2015 Conference Paper

Compatible Connectivity-Augmentation of Planar Disconnected Graphs

• Greg Aloupis
• Luis Barba
• Paz Carmi
• Vida Dujmovic
• Fabrizio Frati
• Pat Morin

SODA Conference 2014 Conference Paper

The Complexity of Order Type Isomorphism

• Greg Aloupis
• John Iacono
• Stefan Langerman
• Özgür Özkan
• Stefanie Wuhrer

The order type of a point set in ℝ d maps each ( d +1)-tuple of points to its orientation (e. g. , clockwise or counterclockwise in ℝ 2 ). Two point sets X and Y have the same order type if there exists a mapping f from X to Y for which every ( d +1)-tuple ( a 1, a 2, …, a d +1 ) of X and the corresponding tuple ( f ( a 1 ), f ( a 2 ), …, f ( a d +1 )) in Y have the same orientation. In this paper we investigate the complexity of determining whether two point sets have the same order type. We provide an O ( n d ) algorithm for this task, thereby improving upon the O ( n ⌊3 d /2⌋ ) algorithm of Goodman and Pollack (1983). The algorithm uses only order type queries and also works for abstract order types (or acyclic oriented matroids). Our algorithm is optimal, both in the abstract setting and for realizable points sets if the algorithm only uses order type queries.

SODA Conference 2009 Conference Paper

Decomposition of multiple coverings into more parts

• Greg Aloupis
• Jean Cardinal
• Sébastien Collette
• Stefan Langerman
• David Orden
• Pedro Ramos 0001

We prove that for every centrally symmetric convex polygon Q, there exists a constant α such that any αk -fold covering of the plane by translates of Q can be decomposed into k coverings. This improves on a quadratic upper bound proved by Pach and Tóth (SoCG'07). The question is motivated by a sensor network problem, in which a region has to be monitored by sensors with limited battery life.