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

وبلاگ تخصصی الگوریتم

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

وبلاگ تخصصی الگوریتم

وبلاگ علمی و مخصوص مباحث الگوریتمی است.
نظر خصوصی نگذارید چون جواب نمی‌دهم نظر عمومی بگذارید بدون نام هم که باشد همانجا جواب می‌دهم.

بایگانی

۱۰۷ مطلب با موضوع «هندسه محاسباتی» ثبت شده است

۰ نظر موافقین ۰ مخالفین ۰ ۰۳ ارديبهشت ۹۹ ، ۱۶:۰۵
سپیده آقاملائی
https://arxiv.org/pdf/2004.03206.pdf
۰ نظر موافقین ۰ مخالفین ۰ ۲۰ فروردين ۹۹ ، ۱۳:۴۹
سپیده آقاملائی
https://arxiv.org/abs/2003.11604
۰ نظر موافقین ۰ مخالفین ۰ ۰۸ فروردين ۹۹ ، ۱۴:۴۳
سپیده آقاملائی

الگوریتم جاروب صفحه برای پیدا کردن تقاطع پاره‌خط‌ها را پیاده‌سازی کنید:
http://page.mi.fu-berlin.de/panos/cg13/l03.pdf

می‌خواهم برای اعداد اعشاری پیاده‌سازی کنم، به جای نقطه تقاطع معادله‌ی خط‌ها را نگه دارم. اینجا آدم تازه می‌فهمد که مقاله‌های لافر در مورد حفظ کردن ساختار توپولوژیکی جواب در حضور داده‌های نادقیق به چه دردی می‌خورد: اگر تقاطعی باشد در کدام جهت رندش کنیم که بدانیم هیچ تقاطعی را از دست نداده‌ایم. البته فکر کنم دقیقاً برای این سوال بررسی نشده. شاید روی آن کار کنیم.

فقط اگر کلید داشته باشیم می‌توانیم از کتابخانه استاندارد استفاده کنیم، چون کلاً آن ساختمان داده‌ها برای اعداد طراحی شده‌اند. حالا مثلاً در الگوریتم جاروب صفحه ما داریم ترتیب یک سری پاره‌خط را نگه می‌داریم که به مرور که جلو می‌رویم ترتیبشان تغییر می‌کند. مشکل این است که چطوری با عدد ترتیب به پاره‌خط‌ها بدهیم که بتوانیم دو تای مجاور را بعد از یک تقاطع جابه‌جا کنیم بدون اینکه بخواهیم دوباره ترتیب همه‌ی پاره‌خط‌ها را عوض کنیم. یک راه‌حل این است که همان اعداد ۱ تا n را بدهیم و برای جابه‌جا کردن هر دو پاره‌خط را حذف کنیم و کلیدهایشان را جابه‌جا کنیم و دوباره اضافه کنیم. مشکل این کار وقتی است که می‌خواهیم نقطه جدید اضافه کنیم، باید روی درخت جستجو کنیم بر حسب y، ولی فقط ترتیب پاره‌خط‌ها را داریم. می‌توانیم تابع مقایسه را دوباره بنویسیم که یک پارامتر دیگه بگیرد که نگه دارد کدام نقطه جدید است و بر اساس y آن مقایسه کند.

۰ نظر موافقین ۰ مخالفین ۰ ۰۳ فروردين ۹۹ ، ۱۳:۴۲
سپیده آقاملائی

http://www1.pub.informatik.uni-wuerzburg.de/eurocg2020/data/uploads/papers/eurocg20_paper_55.pdf

http://www1.pub.informatik.uni-wuerzburg.de/eurocg2020/data/uploads/slides/9b/9b-2-schwarzwald.pdf

https://youtu.be/Xnm91r60IeA

۰ نظر موافقین ۰ مخالفین ۰ ۲۸ اسفند ۹۸ ، ۱۹:۴۵
سپیده آقاملائی
https://youtu.be/dk7B-2lNUME
http://www1.pub.informatik.uni-wuerzburg.de/eurocg2020/data/uploads/papers/eurocg20_paper_68.pdf
۰ نظر موافقین ۰ مخالفین ۰ ۲۸ اسفند ۹۸ ، ۱۹:۴۵
سپیده آقاملائی
http://www1.pub.informatik.uni-wuerzburg.de/eurocg2020/index.php?id=program-1
۰ نظر موافقین ۰ مخالفین ۰ ۲۷ اسفند ۹۸ ، ۱۵:۵۱
سپیده آقاملائی
https://arxiv.org/abs/1903.07196
۰ نظر موافقین ۰ مخالفین ۰ ۲۷ اسفند ۹۸ ، ۱۲:۰۵
سپیده آقاملائی
۰ نظر موافقین ۰ مخالفین ۰ ۱۷ دی ۹۸ ، ۲۲:۱۹
سپیده آقاملائی
https://pure.tue.nl/ws/portalfiles/portal/142608440/thesis_A.A._Popov.pdf
۰ نظر موافقین ۰ مخالفین ۰ ۱۷ دی ۹۸ ، ۲۲:۱۴
سپیده آقاملائی