کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414265 680868 2015 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Computing the L1L1 geodesic diameter and center of a simple polygon in linear time
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Computing the L1L1 geodesic diameter and center of a simple polygon in linear time
چکیده انگلیسی

In this paper, we show that the L1L1 geodesic diameter and center of a simple polygon can be computed in linear time. For the purpose, we focus on revealing basic geometric properties of the L1L1 geodesic balls, that is, the metric balls with respect to the L1L1 geodesic distance. More specifically, in this paper we show that any family of L1L1 geodesic balls in any simple polygon has Helly number two, and the L1L1 geodesic center consists of midpoints of shortest paths between diametral pairs. These properties are crucial for our linear-time algorithms, and do not hold for the Euclidean case.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 48, Issue 6, August 2015, Pages 495–505
نویسندگان
, , , ,