دیگر موارد مکشوفه!

یک سری کتاب در مورد ریاضیات موسیقی و اسلایدهای فرآیند تصادفی و الگوریتم (یک کتاب عجیب که هم الگوریتم است هم اتوماتا و نویسنده هایش motwani و ullman و یک نفر دیگر که نمی شناسم hopcroft هستند!) و کتابهای هندسه محاسباتی که فرصت نکردم کامل کپی کنم اما یک فولدر خالی با عنوان هندسه محاسباتی جبری و یک اسلاید در مورد توپولوژی محاسبات (؟) در آن هست. این هم برنامه ی تعطیلات بین ترم!

اسلایدهای داده کاوی دانشکده ریاضی و علوم کامپیوتر امیرکبیر

داشتم دنبال فیلم هندسه محاسباتی می گشتم اینها را پیدا کردم! :)

دریافت

دریافت

دریافت

دریافت

باید در اولین فرصت بخوانمشان.

یک سری مقاله هم ضمیمه شان است که خیلی زیاد هستند و نمی شود آپلود کرد!

6th Winter School On Computational Geometry February 19-24, 2014

برای من که فایده ای نداره، چون نهایتا سر کلاس یاد نمی گیرم چیز زیادی... بعدم احتمالا با ترم بعد تداخل داره ساعت کلاسهاش.

http://wscg.aut.ac.ir/wscg6/index.php?option=com_content&view=article&id=3&Itemid=2

6th winter school time table

	9:00-10:30	10:30-11:00	11:00-12:30
Feb. 19	Partiotion trees: The basics by Mark de Berg	Coffee break	Computing similarity between two curves by Joachim Gudmundsson
Feb. 20	Partition trees: trade-offs and multi-level structures  by Mark de Berg		Curve/trajectory clustering by Joachim Gudmundsson
Feb. 21	Partition trees: applications by Mark de Berg		Approximating the Frechet distance by Joachim Gudmundsson
Feb. 22	No Lecture
Feb. 23	Locally correct Frechet matching by Joachim Gudmundsson	Coffee break	Arrangements: upper envelopes, single cells and other substructures by Mark de Berg
Feb. 24	Curve segmentation by Joachim Gudmundsson		Arrangements: applications by Mark de Berg

محاسبه مساحت مستطیل های موازی محورهای مختصات با segment tree

مساله به klee's rectangle problem معروف است و راه حل توسط Bentley ارائه شده است.

یک sweep عمودی انجام می دهیم و هر بار اجتماع بازه هایی که داخل مستطیل ها هستند (xشان) را حساب می کنیم. (با segment tree)

این را در اختلاف y این مرحله sweep با مرحله ی قبل ضرب می کنیم و جمع اینها در کل sweep میشه جواب.

کاربردهای line arrangement

مثلث بندی چند ضلعی monotone

درخت سگمنت

می خواهیم پاره خط هایی که با یک مستطیل ورودی تقاطع دارند را پیدا کنیم.

• اول فرض کنید خط ها موازی محورها باشند:

اگر تصویر این خطها را روی محورها در نظر بگیریم، به سادگی می توانیم تشخیص بدهیم با تصویر مستطیل روی محورها تقاطع دارد یا نه.

• اگر پاره خط ها در هر راستای دلخواهی باشند: (نه الزاما موازی محورها: افقی و عمودی)

یک راه حل: interval tree شبیه range tree اما برای پیدا کردن نقطه به جای بازه است (ساخت درخت جدا برای x و y - یک بعدی: بازه ها برگ های درخت جستجوی دودویی اند). چک کردن همه ی پاره خط های این ناحیه برای اینکه جواب باشند یا نه زمانبر است، پس از یک درخت دیگر به نام segment tree استفاده می کنیم.

روش لوکاس:

به ناحیه هایی تقسیم کنیم که جواب در آنها یکی است.

یک بعدی:

ناحیه های سر پاره خط ها و ناحیه های شامل پاره خط های یکسان.

به جای اینکه درخت را روی نقطه های دو سر پاره خط ها بسازیم، روی این بازه ها می سازیم. خود بازه ها در برگ ها نگه داری می شوند و گره های میانی اجتماع بازه های فرزندانشان هستند.

کوئری: پیدا کردن پاره خط هایی که شامل یک x خاص هستند.

در هر گره ی میانی، لیست پاره خط هایی نگهداری می شود که گره ی پدر این گره دیگر شامل آنها نمی شود. یعنی هر پاره خط در بالاترین جای درخت (نزدیک تر به ریشه) نگه داری می شود که کامل شامل آن است.

نحوه ی کوئری زدن:

از ریشه درخت به سمت برگی که شامل نقطه ی کوئری است حرکت کن و همه ی لیست های پاره خط های گره های میانی را به عنوان جواب برگردان!

زمان کوئری: O(logn+k)

تحلیل فضا:

برگ ها: هر پاره خط حداکثر دو سر دارد، پس بازه های ساخته شده O(n) می شود.

گره های میانی: هر پاره خط حداکثر در لیست دو گره وجود دارد. (اثبات: برهان خلف: اگر سه گره باشند، شرط بودن در بالاترین گره به هم می خورد؛ چون بالاترین گره ای که شامل پاره خط است (پدر سه گره) و گره ای که فرزند آن است و همان پاره خط را دارد (پدر دو گره از گره های مساله))

کلا: O(nlogn)

نکته: ساختار درخت شبیه درخت بازه ی دوبعدی است! (در حالت یک بعدی)

مثلث بندی

(واقعا ناراحت کننده است که هیچ کدام از توانایی های من برای هیچ کس ارزش نداره.)

یک چند ضلعی را با رسم کردن یک سری یال به مثلث تقسیم کنیم.

1- پیدا کردن قطر

از سمت چپ ترین راس چند ضلعی شروع می کنیم و راسهای دو طرف آن را به هم وصل می کنیم، (فکر کنم این حلش می کنه:) اگر به هم وصل کردیم و بقیه ضلع ها را قطع نکرد جواب است، وگرنه به سر پاره خطی که قطع کرده وصل می کنیم. (سوال امتحان بود که اشتباه گرفتم با قطر چندضلعی محدب!)

هر بار یک قطر پیدا می کنیم، چند ضلعی به دو قسمت تقسیم می شود، هر کدام از این قسمتها را بازگشتی حل می کنیم.

زمان الگوریتم: پیدا کردن قطر: O(n)

T(n) = T(n-1)+O(n)

T(n) = O(n^2)

1- 2- بهبود: قطری را پیدا کن که هر دو چندضلعی کمتر از 2/3n ضلع داشته باشند.

T(n) = 2T(2/3n)+O(n)

T(n) = O(nlogn)

2- استفاده از تجزیه ذوزنقه بندی

اول ذوزنقه بندی را به دست می آوریم، اگر دو راسی که ذوزنقه را می سازند مال یک پاره خط نباشند، آنها را به هم وصل می کنیم. (شکل بکشید!)

چندضلعی های ساخته شده را مثلث بندی کنید.

چندضلعی های ساخته شده با این روش همه half monotone هستند، یعنی هر خط عمودی آنها را در دو نقطه قطع می کند. با graham scan می توان هر چند ضلعی به این شکل را در زمان خطی مثلث بندی کرد. (graham scan: نقاط را یکی یکی اضافه می کند و ccw بودن کنج ساخته شده را چک می کند.)

زمان الگوریتم:

O(nlogn)+O(n)+O(n) = O(nlogn)

زمان ذوزنقه بندی+زمان اضافه کردن یال به ذوزنقه ها+زمان مثلث بندی چند ضلعی های half monotone

نکته: برای چند ضلعی های دارای سوراخ هم کار می کند.

نکته: می توان زمان sort را حذف کرد.

3- الگوریتم افزایشی تصادفی تغییر یافته (سیدل)

به ذوزنقه بندی یکی یکی پاره خط اضافه می کنیم، اگر این پاره خط شماره ی ceil(n/logn^h) بود که h بین 1 و log*n است، ذوزنقه ی شامل یک سر این پاره خط را پیدا می کنیم و بقیه را از روی آن پیدا می کنیم. زمان آن logk/j می شود که k تعداد ذوزنقه هایی است که قطع می کند و j شماره ی ذوزنقه ی اول است. (یعنی ساختمان داده را به روز می کنیم.)

با این کار زمان الگوریتم nlog*n می شود.

درخت های جستجوی بازه ای

یک مجموعه نقطه داریم در صفحه.

کوئری: تعداد نقاطی که در یک مستطیل می افتند. (اضلاع مستطیل با محورهای مختصات موازی اند.)

یک بعدی: نقاط را مرتب می کنیم و ... .

دو بعدی:

1- k-d tree

اسمش از k dimension tree آمده که به معنی درخت k بعدی است. در حالت دو بعدی، یک عمق در میان x و y است. در هر عمق میانه ی نقاط (از نظر x یا y) به دست می آید و بر اساس آن نقاط را دو دسته می کنیم که فرزندان آن گره می شوند.

زمان ساخت درخت O(nlogn) است و فضای O(n) می گیرد و زمان کوئری آن O(sqrt(n)+k) است.

محاسبه ی زمان کوئری:

T(n) = 2T(n/4)+1 = O(sqrt(n))

نحوه ی کوئری زدن: (پیدا کردن مستطیل با این درخت)

اگر گره ی فعلی برگ است و درون مستطیل می افتد آن را به عنوان جواب برگردان.

در غیر این صورت: اگر فرزند راست گره فعلی کاملا در مستطیل می افتد، کل زیر درخت آن را برگردان؛ در غیر این صورت همین تابع را روی آن انجام بده. اگر فرزند چپ گره فعلی کاملا در مستطیل می افتد، کل زیر درخت آن را برگردان؛ در غیر این صورت همین تابع را روی آن انجام بده.

دلیل زمان کوئری:

چون هر بار که تقسیم می کنیم ممکن است بخشی از مستطیل در یک طرف بیفتد بخش دیگر آن در طرف دیگر.

برای ابعاد دیگر:

یک بعدی: مثل درخت جستجوی دودویی معمولی است فقط دو بار کوئری می زنیم.

سه بعدی: به جای مستطیل مکعب داریم و زمان ساخت درخت nlogn و سایز حافظه n و زمان کوئری n^(1-1/d)+k است.

2- range tree

یک درخت جدا برای x می سازیم و برای نقاط آن زیر درخت (که x آنها در بازه ی مورد نظر است) یک درخت دیگر بر حسب y می سازیم.

تحلیل حافظه: چون هر نقطه در دو گره است (یکبار برای x یکبار برای y ) پس همان O(n) می شود.

تحلیل زمان:

T(n) = 2T(n/2)+O(nlogn)

T(n) = O(nlogn)

طبق حالت دوم قضیه اصلی

n^log(a,b) *logn^k = nlogn

k=1, log(a,b) = 1

اگر به جای اینکه هر بار sort کنیم، فقط یکبار اول این کار را انجام بدهیم (مرتب سازی بر حسب y) و لیست های مرتب شده را به گره های بعدی بدهیم، زمان ساخت درخت به مقدار زیر کاهش پیدا می کند:

T(n) = 2T(n/2)+O(n)

T(n) = O(nlogn)

طبق حالت دوم قضیه اصلی

n^log(a,b) = n

k = 0

کوئری زدن:

اگر گره ی فعلی جواب است آن را برگردان. (اگر برگ است اینجا چک کن)

در غیر این صورت در درخت y جستجو کن و جواب را برگردان.

(اگر غیر برگ است اینجا چک کن.)

زمان کوئری:

logn = زمان پیدا کردن x

logn+k = زمان پیدا کردن y

کلا: O(logn*logn)

ایده کلی و تفاوت با حالت 1 (k-d tree)

از تصویر کردن روی محورها استفاده کردیم. قبلی بیشتر برای پیدا کردن یک نقطه به درد می خورد.

تعمیم: برای d بعد

فضای لازم:

S(d,n) <= 2*S(d,n/2)+S(d-1,n)

S(n) = n*(logn)^(d-1)

برای حلش هم میشه استقرا زد. یعنی فرض کنیم S(d-1,n) = n*(logn)^(d-2) باشه، طبق حالت دوم قضیه اصلی n*(logn)^k که k=d-2 در نتیجه یک logn اضافه میشه و n*(logn)^(k-1) به دست میاد.

حافظه لازم:

T(d,n) <= 2logn*T(d-1,n)+O(logn)

که میشه O(logn^d)

2-2- fractional cascading

هدف: صرفه جویی در زمان باینری سرچ های متوالی روی یک مجموعه

در گره ی ریشه درخت را نگه می داریم، اما درختهای فرزندان را به لیست تبدیل می کنیم.

می توانیم logn ای را که صرف باینری سرچ می کنیم حذف کنیم، به این صورت که لیست هر عمق را به لیست عمق پایینتر با اشاره گر وصل کنیم. (عناصر متناظر را). پس به سادگی می توانیم با دنبال کردن این اشاره گرها به عنصر مورد نظر برسیم. (بدون اینکه نیاز باشد از روی درخت حرکت کنیم.)

این باعث می شود که زمان به O(logn^(d-1)) کاهش پیدا کند. (برای قسمت جستجو روی y و ابعاد بالاتر)

* اگر ساختار داینامیک باشد (حذف و درج داشته باشیم) باید درخت نگه داریم اما باز هم می توانیم همین ایده را پیاده کنیم.

# حالتهای خاص

وقتی که x چند نقطه با هم مساوی باشد (یا y) برای اینکه مشکلی پیش نیاید، در مقایسه ی نقاط مختصات را به ترتیب مقایسه می کنیم. (شبیه مقایسه ی pair در c++)

ارائه ها

به دلیل نامعلومی تصمیم گرفتم ارائه هام رو آپلود کنم.

دریافت
عنوان: fault tolerant clustering

دریافت
عنوان: P3C clustering algorithm
توضیحات: projected + subspace

دریافت
عنوان: online unit clustering
توضیحات: randomized clustering