کتاب هارپلد (فصل ۱)
*نزدیک‌ترین زوج نقاط
اگر دو نقطه درون یک خانه توری بیفتند فاصله‌ی آنها از اندازه خانه توری کمتر است. می‌توانیم همین کار را برای خانه‌هایی که تراکم نقاط بیشتر دارند تکرار کنیم. نسخه تصمیم گیری مسأله فقط می‌خواهد بگوییم جواب از یک مقدار کمتر است یا بیشتر که این کار را با ساخت توری انجام می‌دهیم. جستجوی دودویی روی این مقدار جواب را می‌دهد.
بهبود: جایگشت تصادفی از نقاط را حساب می‌کنیم. به صورت افزایشی نقاط را اضافه می‌کنیم و جواب را به دست می‌آوریم. اگر از قبل بهتر شده بود توری را مجدداً می‌سازیم. (با توجه به مقدار جدید). این کار زمان O(i) در مرحله i-ام می‌گیرد. چون این احتمال 1/i است پس متوسط زمان اجرا
sum i*1/i = sum 1 = n
یعنی خطی است.
*الگوریتم ۲-تقریبی برای دیسک شامل k نقطه
یک توری تطبیق پذیر را به این صورت می‌سازیم که هر قسمت شامل k نقطه باشد و هر کدام از این قسمت‌ها را به قسمت‌های k/4 نقطه دار تقسیم می‌کنیم.
برای این کار از الگوریتم پیدا کردن عنصر با رتبه مشخص استفاده می‌کنیم که زمان O(n log n/k) می‌گیرد که O(n) برای قسمت اول است و در قسمت دوم چون بازگشتی تا جایی پیش می‌رویم که k/4 نقطه بماند زمان آن O(log n/k) می‌شود.
سپس برای هر خانه از رئوس توری کوچکترین دایره شامل k نقطه را پیدا می‌کنیم.
تعداد رأسهای توری (n/k)^2 تا است و برای پیدا کردن کوچکترین دایره شامل نقاط به چک کردن بیش از n نقطه نیاز نخواهیم داشت. پس کلاً زمان O(n (n/k)^2) می‌گیرد.
هر دایره برای اینکه k نقطه داشته باشد باید حداقل ۴ ناحیه را قطع کند. پس حتما شامل یکی از رأسهای توری می‌شود.
بهبود:
با استفاده از توری سلسله مراتبی و ساختاری مشابه skiplist می‌توانیم به زمان خطی برای این مسأله برسیم. این کار را تا جایی ادامه می‌دهیم که k نقطه در آن سطح باقی بمانند.
هیچ خانه توری بیش از 5k نقطه ندارد. (اثبات با رسم ۴ دایره در گوشه‌های خانه توری و دایره محاطی خانه توری+ماکسیمم تعداد نقاطی که در دایره به شعاع خانه توری جا می‌شوند)
جواب را برای توری در هر عمق حساب می‌کنیم (زمان خطی). توری هر مرحله از جواب عمق بالاتر خود به دست آمده است.
ساخت skip-list زمان خطی می‌برد. زمان محاسبه جواب برای هر توری O(k) است. با تلاش فراوان (!) زمان متوسط خطی به دست می‌آید.
*حل تمرین‌های فصل ۱
