Access Restriction

Author Huber, Stefan ♦ Held, Martin
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2011
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Geometric hashing ♦ Motorcycle graph ♦ Stochastic analysis
Abstract In this article, we study stochastic properties of a geometric setting that underpins random motorcycle graphs and use it to motivate a simple but very efficient algorithm for computing motorcycle graphs. An analysis of the mean trace length of $\textit{n}$ random motorcycles suggests that, on average, a motorcycle crosses only a constant number of cells within a &sqrt; $\textit{n}$ × &sqrt; $\textit{n}$ rectangular grid, provided that the motorcycles are distributed sufficiently uniformly over the area covered by the grid. This analysis motivates a simple algorithm for computing motorcycle graphs: We use the standard priority-queue--based algorithm and enhance it with geometric hashing by means of a rectangular grid. If the motorcycles are distributed sufficiently uniformly, then our stochastic analysis predicts an $\textit{O}(\textit{n}$ log $\textit{n})$ runtime. Indeed, extensive experiments run on 22,000 synthetic and real-world datasets confirm a runtime of less than $10^{™5}$ $\textit{n}$ log $\textit{n}$ seconds for the vast majority of our datasets on a standard PC. Further experiments with our software, Moca, also confirm the mean trace length and average number of cells crossed by a motorcycle, as predicted by our analysis. This makes Moca the first implementation that is efficient enough to be applied in practice for computing motorcycle graphs of large datasets. Actually, it is easy to extend Moca to make it compute a generalized version of the original motorcycle graph, thus enabling a significantly larger field of applications.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2011-08-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 16
Page Count 17
Starting Page 1.1
Ending Page 1.17

Open content in new tab

   Open content in new tab
Source: ACM Digital Library