Detecting hotspots in geographic networks

K. Buchin, S. Cabello, J. Gudmundsson, M. Löffler, J. Luo, G. Rote, R.I. Silveira, B. Speckmann, T. Wolle

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

9 Citaten (Scopus)
1 Downloads (Pure)


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.
Originele taal-2Engels
TitelAdvances in GIScience (Proceedings of the 12th AGILE Conference, Hannover, Germany, June 2-5, 2009)
RedacteurenM. Sester, L. Bernard, V. Paelke
Plaats van productieBerlin
ISBN van geprinte versie978-3-642-00317-2
StatusGepubliceerd - 2009

Publicatie series

NaamLecture Notes in Geoinformation and Cartography
ISSN van geprinte versie1863-2246


Duik in de onderzoeksthema's van 'Detecting hotspots in geographic networks'. Samen vormen ze een unieke vingerafdruk.

Citeer dit