Performing multicut on walkable environments: Obtaining a minimally connected multi-layered environment from a walkable environment

Arne Hillebrand; Marjan van den Akker; Roland Geraerts; Han Hoogeveen

doi:10.1007/978-3-319-48749-6_23

Performing multicut on walkable environments: Obtaining a minimally connected multi-layered environment from a walkable environment

Arne Hillebrand^*, Marjan van den Akker, Roland Geraerts, Han Hoogeveen

^*Corresponding author for this work

Algorithms and Complexity

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

A multi-layered environment is a representation of the walkable space in a 3D virtual environment that comprises a set of twodimensional 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.

Original language	English
Title of host publication	Combinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Proceedings
Editors	Minming Li, Lusheng Wang, T-H. Hubert Chan
Publisher	Springer
Pages	311-325
Number of pages	15
Volume	10043
ISBN (Print)	9783319487489
DOIs	https://doi.org/10.1007/978-3-319-48749-6_23 https://doi.org/10.1007/978-3-319-48749-6_23
Publication status	Published - 2016
Event	10th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2016 - Hong Kong, China Duration: 16 Dec 2016 → 18 Dec 2016

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10043 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	10th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2016
Country/Territory	China
City	Hong Kong
Period	16/12/16 → 18/12/16

Keywords

Simple Path
Visibility Graph
Graph Reduction
Crowd Simulation
Walkable Environment

Access to Document

Performing Multicut on Walkable Environments: Obtaining a Minimally Connected Multi-Layered EnAccepted author manuscript, 3.35 MB
Performing Multicut on Walkable EnvironmentsFinal published version, 1.37 MBLicence: Taverne

Cite this

Hillebrand, A., van den Akker, M., Geraerts, R., & Hoogeveen, H. (2016). Performing multicut on walkable environments: Obtaining a minimally connected multi-layered environment from a walkable environment. In M. Li, L. Wang, & T.-H. H. Chan (Eds.), Combinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Proceedings (Vol. 10043, pp. 311-325). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10043 LNCS). Springer. https://doi.org/10.1007/978-3-319-48749-6_23, https://doi.org/10.1007/978-3-319-48749-6_23

Hillebrand, Arne ; van den Akker, Marjan ; Geraerts, Roland et al. / Performing multicut on walkable environments : Obtaining a minimally connected multi-layered environment from a walkable environment. Combinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Proceedings. editor / Minming Li ; Lusheng Wang ; T-H. Hubert Chan. Vol. 10043 Springer, 2016. pp. 311-325 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{58f2c7fa6d1a4b36a0f7b78544591bd0,

title = "Performing multicut on walkable environments: Obtaining a minimally connected multi-layered environment from a walkable environment",

abstract = "A multi-layered environment is a representation of the walkable space in a 3D virtual environment that comprises a set of twodimensional 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.",

keywords = "Simple Path, Visibility Graph, Graph Reduction, Crowd Simulation, Walkable Environment",

author = "Arne Hillebrand and {van den Akker}, Marjan and Roland Geraerts and Han Hoogeveen",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2016.; 10th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2016 ; Conference date: 16-12-2016 Through 18-12-2016",

year = "2016",

doi = "10.1007/978-3-319-48749-6_23",

language = "English",

isbn = "9783319487489",

volume = "10043",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "311--325",

editor = "Minming Li and Lusheng Wang and Chan, {T-H. Hubert}",

booktitle = "Combinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Proceedings",

address = "Germany",

}

Hillebrand, A, van den Akker, M , Geraerts, R & Hoogeveen, H 2016, Performing multicut on walkable environments: Obtaining a minimally connected multi-layered environment from a walkable environment. in M Li, L Wang & T-HH Chan (eds), Combinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Proceedings. vol. 10043, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10043 LNCS, Springer, pp. 311-325, 10th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2016, Hong Kong, China, 16/12/16. https://doi.org/10.1007/978-3-319-48749-6_23, https://doi.org/10.1007/978-3-319-48749-6_23

Performing multicut on walkable environments: Obtaining a minimally connected multi-layered environment from a walkable environment. / Hillebrand, Arne; van den Akker, Marjan ; Geraerts, Roland et al.
Combinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Proceedings. ed. / Minming Li; Lusheng Wang; T-H. Hubert Chan. Vol. 10043 Springer, 2016. p. 311-325 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10043 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Performing multicut on walkable environments

T2 - 10th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2016

AU - Hillebrand, Arne

AU - van den Akker, Marjan

AU - Geraerts, Roland

AU - Hoogeveen, Han

N1 - Publisher Copyright: © Springer International Publishing AG 2016.

PY - 2016

Y1 - 2016

N2 - A multi-layered environment is a representation of the walkable space in a 3D virtual environment that comprises a set of twodimensional 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.

AB - A multi-layered environment is a representation of the walkable space in a 3D virtual environment that comprises a set of twodimensional 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.

KW - Simple Path

KW - Visibility Graph

KW - Graph Reduction

KW - Crowd Simulation

KW - Walkable Environment

UR - http://www.scopus.com/inward/record.url?scp=85007203562&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-48749-6_23

DO - 10.1007/978-3-319-48749-6_23

M3 - Conference contribution

AN - SCOPUS:85007203562

SN - 9783319487489

VL - 10043

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 311

EP - 325

BT - Combinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Proceedings

A2 - Li, Minming

A2 - Wang, Lusheng

A2 - Chan, T-H. Hubert

PB - Springer

Y2 - 16 December 2016 through 18 December 2016

ER -

Hillebrand A, van den Akker M , Geraerts R , Hoogeveen H. Performing multicut on walkable environments: Obtaining a minimally connected multi-layered environment from a walkable environment. In Li M, Wang L, Chan THH, editors, Combinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Proceedings. Vol. 10043. Springer. 2016. p. 311-325. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-48749-6_23, 10.1007/978-3-319-48749-6_23

Performing multicut on walkable environments: Obtaining a minimally connected multi-layered environment from a walkable environment

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this