Home // MOBILITY 2022, The Twelfth International Conference on Mobile Services, Resources, and Users // View article

Combined Algorithm for Voronoi Diagram Construction in Application to Dynamic Ride Sharing

Authors:
Anton Butenko
Jorge Marx Gómez

Keywords: Voronoi diagram; dynamic ride sharing

Abstract:
A standard Voronoi diagram decomposes a plane into cells with a common closest site. This structure is widely used in computational geometry in application to the nearest neighbor problem. Using Euclidean metric is the most straightforward solution, however, in an urban environment, it may lead to insufficient accuracy that is crucial in applications such as dynamic ride sharing. Deviations in determining the nearest meeting point are especially significant under the presence of obstacles: water reservoirs, railway tracks, highways, industrial zones, as well as hilly terrain. Here, we propose a combined approach for a city Voronoi diagram construction in a generalized metric space. A transportation network is modeled as a weighted graph, so that the route consists of a foot-walking part and the shortest path in the graph. The presented algorithm constructs a continuous Voronoi diagram for a plane using the individual Voronoi cells graph as generator objects. Evaluation for the specific city topography shows that the described algorithm provides more accurate results in comparison with the standard Voronoi diagram.

Pages: 5 to 8

Copyright: Copyright (c) IARIA, 2022

Publication date: June 26, 2022

Published in: conference

ISSN: 2308-3468

ISBN: 978-1-61208-962-1

Location: Porto, Portugal

Dates: from June 26, 2022 to June 30, 2022