**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Publication# On finding another room-partitioning of the vertices

Abstract

Let T be a triangulated surface given by the list of vertex-triples of its triangles, called rooms. A room-partitioning of T is a subset R of the rooms such that each vertex of T is in exactly one room in R. We prove that if T has a room-partitioning R, then there is another room-partitioning of T which is different from R. The proof is a simple algorithm which walks from room to room, which however we show to be exponential by constructing a sequence of (planar) instances, where the algorithm walks from room to room an exponential number of times relative to the number of rooms in the instance. We unify the above theorem with Nash’s theorem stating that a 2-person game has an equilibrium, by proving a combinatorially simple common generalization.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (21)

Related MOOCs (2)

Related publications (32)

First-person shooter

First-person shooter (FPS) is a sub-genre of shooter video games centered on gun and other weapon-based combat in a first-person perspective, with the player experiencing the action through the eyes of a protagonist or antagonist which is armed, and then controlling the player character in a three-dimensional space. The genre shares common traits with other shooter games, and in turn falls under the action game genre. Since the genre's inception, advanced 3D and pseudo-3D graphics have challenged hardware development, and multiplayer gaming has been integral.

Third-person shooter

Third-person shooter (TPS) is a subgenre of 3D shooter games in which the gameplay consists primarily of shooting. It is closely related to first-person shooters, but with the player character visible on-screen during play. While 2D shoot 'em up games also employ a third-person perspective, the TPS genre is distinguished by having the game presented with the player's avatar as a primary focus of the camera's view. A third-person shooter is a game structured around shooting, and in which the player can see the avatar on-screen in a third-person view.

Stealth game

A stealth game is a type of video game in which the player primarily uses stealth to avoid or overcome opponents. Games in the genre typically allow the player to remain undetected by hiding, sneaking, or using disguises. Some games allow the player to choose between a stealthy approach or directly attacking antagonists, but rewarding the player for greater use of stealth. The genre has employed espionage, counter-terrorism, and rogue themes, with protagonists that are special forces operatives, special agents, secret agents, thieves, ninjas, or assassins.

Trigonometric Functions, Logarithms and Exponentials

Ce cours donne les connaissances fondamentales liées aux fonctions trigonométriques, logarithmiques et exponentielles. La présentation des concepts et des propositions est soutenue par une grande gamm

Trigonometric Functions, Logarithms and Exponentials

Ce cours donne les connaissances fondamentales liées aux fonctions trigonométriques, logarithmiques et exponentielles. La présentation des concepts et des propositions est soutenue par une grande gamm

Many modern services need to routinely perform tasks on a large scale. This prompts us to consider the following question:
How can we design efficient algorithms for large-scale computation?
In this thesis, we focus on devising a general strategy to addr ...

Experiencing a body part as one's own, i.e., body ownership, depends on the integration of multisensory bodily signals (including visual, tactile, and proprioceptive information) with the visual top down signals from peripersonal space. Although it has bee ...

Daniel Kressner, Stefano Massei, Alice Cortinovis

This work is concerned with approximating matrix functions for banded matrices, hierarchically semiseparable matrices, and related structures. We develop a new divide-and-conquer method based on (rational) Krylov subspace methods for performing low-rank up ...