کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414121 680813 2016 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Distance-sensitive planar point location
ترجمه فارسی عنوان
محل نقطه مسطح حساس به فاصله
کلمات کلیدی
محل نقطه؛ چاردرخت؛ تولید مش
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

Let SS be a connected planar polygonal subdivision with n   edges that we want to preprocess for point-location queries, and where we are given the probability γiγi that the query point lies in a polygon PiPi of SS. We show how to preprocess SS such that the query time for a point p∈Pip∈Pi depends on γiγi and, in addition, on the distance from p   to the boundary of PiPi—the further away from the boundary, the faster the query. More precisely, we show that a point-location query can be answered in time O(min⁡(log⁡n,1+log⁡area(Pi)γiΔp2)), where ΔpΔp is the shortest Euclidean distance of the query point p   to the boundary of PiPi. Our structure uses O(n)O(n) space and O(nlog⁡n)O(nlog⁡n) preprocessing time. It is based on a decomposition of the regions of SS into convex quadrilaterals and triangles with the following property: for any point p∈Pip∈Pi, the quadrilateral or triangle containing p   has area Ω(Δp2). For the special case where SS is a subdivision of the unit square and γi=area(Pi)γi=area(Pi), we present a simpler solution that achieves a query time of O(min⁡(log⁡n,log⁡1Δp2)). The latter solution can be extended to convex subdivisions in three dimensions.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 54, April 2016, Pages 17–31
نویسندگان
, , , , ,