TY - GEN

T1 - Detecting hotspots in geographic networks

AU - Buchin, K.

AU - Cabello, S.

AU - Gudmundsson, J.

AU - Löffler, M.

AU - Luo, J.

AU - Rote, G.

AU - Silveira, R.I.

AU - Speckmann, B.

AU - Wolle, T.

PY - 2009

Y1 - 2009

N2 - We study a point pattern detection problem on networks, motivated by geographical analysis tasks, such as crime hotspot detection. Given a network N (for example, a street, train, or highway network) together with a set of sites which are located on the network (for example, accident locations or crime scenes), we want to find a connected subnetwork F of N of small total length that contains many sites. That is, we are searching for a subnetwork F that spans a cluster of sites which are close with respect to the network distance.
We consider different variants of this problem where N is either a general graph or restricted to a tree, and the subnetwork F that we are looking for is either a simple path, a path with self-intersections at vertices, or a tree. Many of these variants are NP-hard, that is, polynomial-time solutions are very unlikely to exist. Hence we focus on exact algorithms for special cases and efficient algorithms for the general case under realistic input assumptions.

AB - We study a point pattern detection problem on networks, motivated by geographical analysis tasks, such as crime hotspot detection. Given a network N (for example, a street, train, or highway network) together with a set of sites which are located on the network (for example, accident locations or crime scenes), we want to find a connected subnetwork F of N of small total length that contains many sites. That is, we are searching for a subnetwork F that spans a cluster of sites which are close with respect to the network distance.
We consider different variants of this problem where N is either a general graph or restricted to a tree, and the subnetwork F that we are looking for is either a simple path, a path with self-intersections at vertices, or a tree. Many of these variants are NP-hard, that is, polynomial-time solutions are very unlikely to exist. Hence we focus on exact algorithms for special cases and efficient algorithms for the general case under realistic input assumptions.

U2 - 10.1007/978-3-642-00318-9_11

DO - 10.1007/978-3-642-00318-9_11

M3 - Conference contribution

SN - 978-3-642-00317-2

T3 - Lecture Notes in Geoinformation and Cartography

SP - 217

EP - 231

BT - Advances in GIScience (Proceedings of the 12th AGILE Conference, Hannover, Germany, June 2-5, 2009)

A2 - Sester, M.

A2 - Bernard, L.

A2 - Paelke, V.

PB - Springer

CY - Berlin

ER -