Performing Multicut on Walkable Environments

A multi-layered environment is a representation of the walkable space in a 3D virtual environment that comprises a set of two-dimensional layers together with the locations where the different layers touch, which are called connections. This representation can be used for crowd simulations, e.g. to determine evacuation times in complex buildings. Since the execution times of many algorithms depend on the number of connections, we will study multi-layered environments with a minimal number of connections. We show how finding a minimally connected multi-layered environment can be formulated as an instance of the multicut problem. We will prove that finding a minimally connected multi-layered environment is an NP-Hard problem. Lastly, we will present techniques which shrink the size of the underlying graph by removing redundant information. These techniques decrease the input size for algorithms that use this representation for finding multi-layered environments.

1. 1.

   https://3dwarehouse.sketchup.com/model.html?id= \(\{\)13c3078fa52d14554b9e177bc9ee06a9, 2ac949d235d65acb46697ff0ff0b9b2c, 33b2c337108275568c09573a9753f4fd\(\}\).

Authors and Affiliations

1. Institute of Information and Computing Sciences, Utrecht University, 3508 TA, Utrecht, The Netherlands

   Arne Hillebrand, Marjan van den Akker, Roland Geraerts & Han Hoogeveen

Corresponding author

Correspondence to Arne Hillebrand .

Editors and Affiliations

1. University of Hong Kong, Hong Kong, China

   T-H. Hubert Chan

2. City University of Hong Kong, Hong Kong, China

   Minming Li

3. City University of Hong Kong, Hong Kong, China

   Lusheng Wang

A Proof of STACK-REMOVE

Theorem 2

Given a weighted WEG \(G = (V, E, O, w)\), vertex v with \(N_v = \{ n_v, n_v' \}\), vertex w with \(N_w = \{n_w, n_w' \}\), \(\{(v, w)\), \((n_v, n_w)\), \((n_v', n_w')\}\) \(\subseteq O\) and \(w(e) = 1\) for all \(e \in E\). The optimal cut set \(\mathcal {C}'\) for \(G'= (V,E,O', w)\) with \(O' = O\!\setminus \!(v,w)\), either is also optimal for G, or can be adjusted to an optimal cut set \(\mathcal {C}\) for G.

Proof

Assume we have the WEG \(G' = (V, E, O',w)\), with \(O' = O\!\setminus \!(v,w)\). Furthermore, we will also assume that we have found a MICLE for \(G'\) with the cut set \(\mathcal {C}'\). Are all paths \([v \rightarrow w]\) cut by \(\mathcal {C}'\)? If not, how can we change \(\mathcal {C}'\) without increasing the weight so that these paths are cut? This situation is also illustrated in Fig. 5.

First, we observe that all vertex-disjoint paths \([v \rightarrow w]\) can be split into four categories, namely \([v, n_v \rightarrow n_w, w]\), \([v, n_v' \rightarrow n_w', w]\), \([v, n_v \rightarrow n_w', w]\) and \([v, n_v' \rightarrow n_w, w]\). Categories \([v, n_v \rightarrow n_w, w]\) and \([v, n_v' \rightarrow n_w', w]\) will be cut by \(\mathcal {C}'\), because the vertex-disjoint paths \([n_v \rightarrow n_w]\) and \([n_v' \rightarrow n_w']\) need to be cut for any valid MICLE of \(G'\). But what about the paths \([v, n_v \rightarrow n_w', w]\) and \([v, n_v' \rightarrow n_w, w]\)? We know the following groups of paths will be cut using edges of \(\mathcal {C}'\): (a) \([ n_v \rightarrow n_w', w, n_w]\); (b) \([ n_v' \rightarrow n_w, w, n_w']\); (c) \([ n_v, v, n_v' \rightarrow n_w]\); (d) \([ n_v', v, n_v \rightarrow n_w']\).

This fact does not guarantee that the vertex-disjoint paths \([v, n_v \rightarrow n_w', w]\) and \([v, n_v' \rightarrow n_w, w]\) are cut by \(\mathcal {C}'\). The paths \([v, n_v \rightarrow n_w', w]\) and \([v, n_v' \rightarrow n_w, w]\) are definitely cut when \(\mathcal {C}'\) contains at least one edge of all vertex-disjoint paths \([n_v \rightarrow n_w']\) and \([n_v' \rightarrow n_w]\). If this is not the case, we have one of the following three situations:

1. 1.

   The paths \([n_v \rightarrow n_w']\) are cut by \(\mathcal {C}'\), but the paths \([n_v' \rightarrow n_w]\) are not;

2. 2.

   The paths \([n_v' \rightarrow n_w]\) are not cut by \(\mathcal {C}'\), but the paths \([n_w \rightarrow n_v]\) are;

3. 3.

   Both the paths from \([n_v \rightarrow n_w']\) and \([n_v' \rightarrow n_w]\) are not cut by \(\mathcal {C}'\).

For these three remaining situations we can replace edges from \(\mathcal {C}'\) to also cut all paths \([v \rightarrow w]\) without increasing the weight of \(\mathcal {C}'\) and cutting all paths from O and thus obtaining the cut set \(\mathcal {C}\) for G.

For the first situation, we know that the edges \((n_v, v)\) and \((n_w', w)\) need to be in \(\mathcal {C}'\) to cut the paths of type (b) and (c). Instead of adding the edges \((n_v, v)\) and \((n_w', w)\) to \(\mathcal {C}'\), we can add the edges \((n_v', v)\) and \((n_w, w)\) to \(\mathcal {C}'\) without increasing the weight of \(\mathcal {C}'\). When we do this the overlapping vertices of \(G'\) will still be separated, but we also separated v from w without increasing the weight of \(\mathcal {C}'\). The second situation can be handled analogously.

When we have the third situation, we know that one of the edges \(\{(n_w, w),\)

\( (w, n_w') \}\) needs to be in \(\mathcal {C}'\) to cut the paths of types (a) and (b), and one of the edges \(\{(n_v, v), (v, n_v') \}\) to cut the paths of type (c) and (d). When we just pick the edges \((v, n_v)\) and \((w, n_w)\), we will once again not change the size of \(\mathcal {C}'\) and still separate all overlaps of \(O'\), but also all overlaps of O.   \(\square \)

The same trick can be applied to prove that overlaps can also be removed in a stack of structures. This can be proven using exactly the same steps as before and can only be applied under the same restrictions.

Reprints and permissions

© 2016 Springer International Publishing AG

Policies and ethics