کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
433815 689633 2016 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Tight bounds in the quadtree complexity theorem and the maximal number of pixels crossed by a curve of given length
ترجمه فارسی عنوان
محدوده تنگ در قضیه پیچیدگی چهار بعدی و حداکثر تعداد پیکسل های عبور شده توسط منحنی طول داده شده
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

The main purpose of this work is to determine the exact maximum number of pixels (a bi-dimensional sequence of unit squares tiling a plane) that a rectifiable curve of given length l   can cross. In other words, given l∈Rl∈R, we provide the value N(l)N(l) of the maximal cardinality of the digital cover of a rectifiable curve of length l  . The optimal curves are polygonal curves with integer vertices, 0, 1 or 2 vertical or horizontal steps and an arbitrary number of diagonal steps. We also report the properties of the staircase function N(l)N(l), which is affinely periodic in the sense that N(l+2)=N(l)+3 and a bound N(l)≤4+32l.Our second aim is to look at the restricted class of closed curves and offer some conjectures on the maximum number Nclosed(l)Nclosed(l) of pixels that a closed curve of length l can cross.This work finds its application in the quadtree complexity theorem. This well-known result bounds the number of quads with a shape of perimeter p   by 16q−11+16p16q−11+16p. However, this linear bound is not tight. From our new upper bound Nclosed(l)≤N(l)≤4+32l we derive a new improved multiresolution complexity theorem: Number(quads)≤16q−11+62p. Lastly, we show that this new bound is tight up to a maximal error of 16(q−1)16(q−1).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 624, 18 April 2016, Pages 41–55
نویسندگان
, , ,