### Motorcycle graphs: Stochastic properties motivate an efficient yet simple implementationMotorcycle graphs: Stochastic properties motivate an efficient yet simple implementation

Access Restriction
Subscribed

 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

Source: ACM Digital Library