Home // International Journal On Advances in Telecommunications, volume 15, numbers 3 and 4, 2022 // View article

Combined Algorithm for Voronoi Diagram Construction as it Applies to Dynamic Ride Sharing

Authors:
Anton Butenko
Jorge Marx Gómez

Keywords: Voronoi diagram; dynamic ride sharing

Abstract:
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 urban environment it may lead to insufficient accuracy that is crucial in such applications 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 city Voronoi diagram construction in general metric space. A transportation network is modelled as weighted graph, so that the route consists of a foot-walking part and shortest path in graph. Presented algorithm constructs continuous Voronoi diagram for a plane using the individual graph Voronoi cells as generator objects. Evaluation for the specific city topography shows that the described algorithm provides more accurate results in comparasion with the standart Voronoi diagram.

Pages: 52 to 59

Copyright: Copyright (c) to authors, 2022. Used with permission.

Publication date: December 31, 2022

Published in: journal

ISSN: 1942-2601