کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414748 681020 2014 26 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On d-regular schematization of embedded paths
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On d-regular schematization of embedded paths
چکیده انگلیسی

Motivated by drawing route sketches, we consider the d-regular path schematization problem. For this problem we are given an embedded path P (e.g., a route in a road network) and a positive integer d. The goal is to find a d-schematized embedding of P   in which the orthogonal order of all vertices in the input is preserved and in which every edge has a direction that is an integer multiple of (90/d)°(90/d)°. We show that deciding whether a path can be d-schematized is NP-complete for any positive integer d.Despite the NP-hardness of the problem we still want to be able to generate route sketches and thus need to solve the d-regular path schematization problem. We explore two different algorithmic approaches, both of which consider two additional quality constraints: We require that every edge is drawn with a user-specified minimum length and we want to maximize the number of edges that are drawn with their preferred direction. The first algorithmic approach restricts the input paths to be axis-monotone. We show that there exists a polynomial-time algorithm that solves the d-regular path schematization problem for this restricted class of embedded paths. We extend this approach by a heuristic such that it can handle arbitrary simple paths. However, for the second step we cannot guarantee that the orthogonal order of the input embedding is maintained. The second approach is a formulation of the d-regular path schematization problem as a mixed integer linear program. Finally, we give an experimental evaluation which shows that both approaches generate reasonable route sketches for real-world data.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 47, Issue 3, Part A, April 2014, Pages 381–406
نویسندگان
, , , , ,