عنوان پایان‌نامه
گراف k - نزدیکترین همسایگی
- رشته تحصیلی
- ریاضی‌محض
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس علوم شماره ثبت: 5722;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 69059
- تاریخ دفاع
- ۲۶ خرداد ۱۳۹۴
- دانشجو
- فرناز قنبری
- استاد راهنما
- محمدرضا درفشه
- چکیده
- یک مجموعه ازn تا گوی با بعد d یک سیستم k-گانه را تشکیل می دهند اگر هیچ نقطه ای از فضا با بیش از k گوی پوشیده نشود. نشان داده می شود که برای هر سیستم k-گان? ? یک کر? S وجود دارد که با حداکثر O(k^(1/d) n^(1-1/d)) گوی از ?اشتراک دارد و مابقی اعضای? را به دو بخش تقسیم می کند. به ترتیب آن هایی که در داخل و آن هایی که در خارج از کر? S هستند. بنابراین بزرگترین بخش شامل n(1-1/(d+2)) گوی است. مرز O(k^(1/d) n^(1-1/d) ) بهترین تخمین برای هردوی n و k است. همچنین یک الگوریتم ساد? تصادفی برای یافتن چنین کره ای با O(n) مرتبه ارائه می شود. حال نتیجه ای که بدست می آید این است که هر گراف k-نزدیکترین هسایگی با n نقطه با بعد d یک جداساز از مرتب? O(k^(1/d) n^(1-1/d)) دارد. انگیز? این تحقیق قضی? جداسازی مسطح لیپتون و تارجان ، مشخص? هندسی از گراف های مسطح کوبی و تقسیم هندسی و حل آن است. این نتیجه با نتیج? کوبی که می گوید هر گراف مسطح سه گوش یکریخت با گراف تقاطع دیسک بندی نه تنها یک اثبات هندسی جدید از قضی? جداسازی مسطح لیپتون و تارجان ارائه می دهد بلکه آن را به بعد های بالاتر تعمیم می دهد و همچنین از این الگوریتم جداسازی برای نقطه یابی و تقسیم هندسی و حل آن در فضای ابعاد ثابت استفاده می شود. قابل ذکر است که مرجع اصلی مطالعات ما، مقال? [29] است.کلمات کلیدی: گراف های نزدیکترین همسایگی، کره بندی، سیستم k-گانه، جداسازی کره، قضی? جداسازی مسطح، نقطه یابی، تقسیم هندسی و حل آن،
- Abstract
- Abstract A collection of n balls in d dimensions forms a k-ply system if no point in the space is covered by more than k balls. It’s shown that for every k-ply system ?, there is a sphere S that intersects at most O(k 1/??n 1?1/d ) balls of ? and divides the remainder of ? into two parts: those in the interior and those in the exterior of the sphere S, respectively, so that the larger part contains at most (1-1/(d+2)))n balls. This bound of O(k 1/??n 1?1/d ) is the best possible in both n and k. We also present a simple randomized algorithm to find such a sphere in O(n) time. Motivations of this work are the planar separator theorem of Lipton and Tarjan, the geometric characterization of planar graphs of Koebe and geometric divide and conquer. Our result implies that every k-nearest neighbor graphs of n points in d dimensions has a separator of size O(k 1/??n 1?1/d ). In conjunction with a result of Koebe that every triangulated planar graph is isomorphic to the intersection graph of a disk-packing, our result not only gives a new geometric proof of the planar separator theorem of Lipton and Tarjan, but also generalizes it to higher dimensions. The separator algorithm can be used for point location and geometric divide and conquer in a fixed dimensional space.
