Chamfer Distance

http://www.cs.cornell.edu/courses/cs664/2008sp/handouts/cs664-8-binary-matching.pdf

تصویر کردن ۳ بعد روی ۲ بعد

http://web.iitd.ac.in/~hegde/cad/lecture/L9_persproj.pdf

به دست آوردن ناحیه قابل دید ۳ بعدی مثل تصویر کردن یک شکل ۳ بعدی روی یک صفحه ۲ بعدی است، که اینجا صفحه‌ی ۲ بعدی همان وجه است و شکل ۳ بعدی خود ناحیه است.

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

راستی اسم الگوریتم‌ها هم z-buffer و painter's algorithm بود.

Sketching, streaming, and sub-linear space algorithms

http://people.csail.mit.edu/indyk/ita-web.pdf

ساختارهای ضمنی در هندسه ابعاد بالا

مرجع: http://people.csail.mit.edu/indyk/neumann.pdf

affine transformation

http://en.wikipedia.org/wiki/Affine_transformation

In geometry, an affine transformation, affine map^[1] or an affinity (from the Latin, affinis, "connected with") is a function between affine spaces which preserves points, straight lines and planes. Also, sets of parallel lines remain parallel after an affine transformation. An affine transformation does not necessarily preserve angles between lines or distances between points, though it does preserve ratios of distances between points lying on a straight line.

محدب

http://en.wikipedia.org/wiki/Convex_set

http://en.wikipedia.org/wiki/Geodesic_convexity

http://en.wikipedia.org/wiki/Convex_metric_space

http://en.wikipedia.org/wiki/Intrinsic_metric

ellipsoid method (برای بار هزارم!)

http://math.mit.edu/~goemans/18433S09/ellipsoid.pdf

ترکیبیات چندوجهی

http://math.mit.edu/~goemans/18433S13/polyhedral.pdf

بهینه سازی ترکیبیاتی

http://www-math.mit.edu/~goemans/18433S13/18433.html

هرس پارامتری به همراه LP

مرجع: فصل ۱۷ کتاب وزیرانی (سوال تمرین زمانبندی روی ماشین‌های مستقل)

اینجا LP برای مسأله جواب (تقریبی) نمی‌دهد (integrality gap نامحدود دارد یعنی نسبت جواب LP و جواب بهینه نامحدود است).

پس خودمان کاری می‌کنیم که تقریب مورد نظرمان اتفاق بیفتد. برای اینکه یک جواب تقریبی از جواب بهینه باشد، طبق مطالب فصل ۱ و ۲ باید تقریبی از کران مسأله باشد. در کمال بدبختی ما این کران را هم نداریم. برای همین یک پارامتر را می‌گیریم که بتواند کران مناسبی برای مسأله باشد (ولی نمی‌توانیم در زمان کمی حسابش کنیم) و روی آن مثلاً جستجوی دودویی (یا هر جستجوی دیگری!) به کار می‌بریم تا تقریبی از این پارامتر به دست بیاید. در نتیجه با تقریب زدن این پارامتر، می‌توانیم مسأله را هم تقریب بزنیم. (خلاصه اینکه در دو ضرب مسأله را حل می‌کنیم.)

البته از LP هم این استفاده را می‌کنیم که نقاط صحیح جواب را به دست بیاوریم و فقط دنبال بقیه جواب بگردیم.