Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen

سریعترین راه برای تعیین نزدیکترین همسایه مجموعه ای از نقاط چیست؟ چگونه تقاطع دو چند ضلعی را محاسبه کنیم؟ چگونه یک هدف را در یک محیط ناشناخته پیدا می کنید؟

هندسه محاسباتی، شاخه ای از علوم کامپیوتر که توسعه آن در حدود سال 1975 آغاز شد و از آن زمان تاکنون دوره پرتلاطمی را طی کرده است، به این سوالات و سوالات مشابه می پردازد. به دلایل خوب: از یک طرف، پرداختن به مسائل هندسی بسیار جذاب است. اغلب لازم است که ساختارهای پنهان را قبل از ایجاد یک روش راه حل کارآمد کشف کنیم. از سوی دیگر، سؤالات بررسی شده مستقیماً با حوزه های کاربردی مانند پردازش تصویر، گرافیک رایانه ای، سیستم های اطلاعات جغرافیایی و روباتیک مرتبط هستند.

این کتاب درسی مقدمه ای بر تکنیک های الگوریتمی پرکاربرد مانند جارو، تقسیم و غلبه کن و ساخت و ساز افزایشی تصادفی، پویاسازی، تحلیل هزینه مستهلک و تحلیل رقابتی. این کتاب ساختارهای هندسی مهمی مانند بدنه محدب، نمودار ورونوی و مثلث سازی دلون و همچنین ساختارهای داده با ابعاد بالاتر را معرفی می کند.

این کتاب بر اساس سخنرانی هایی است که نویسنده به مدت 12 سال در دانشگاه های مختلف ارائه کرده است. این ویرایش دوم به طور کامل اصلاح شده است. این شامل بیش از 220 تصویر و بیش از 60 تمرین آسان تا متوسط ​​با راه حل ها است. علاوه بر این، یک آزمایشگاه هندسه با اپلت‌های تعاملی جاوا فرصت آزمایش با ساختارها و الگوریتم‌های هندسی را ارائه می‌دهد

Wie bestimmt man in einer Menge von Punkten am schnellsten zu jedem Punkt seinen nächsten Nachbarn? Wie lässt sich der Durchschnitt von zwei Polygonen berechnen? Wie findet man ein Ziel in unbekannter Umgebung?

Mit solchen und ähnlichen Fragen beschäftigt sich die Algorithmische Geometrie, ein Teilgebiet der Informatik, dessen Entwicklung etwa 1975 begann und seitdem einen stürmischen Verlauf genommen hat. Aus gutem Grund: Zum einen ist die Beschäftigung mit geometrischen Problemen sehr reizvoll; oft gilt es, verborgene Strukturen aufzudecken, bevor ein effizientes Lösungsverfahren entwickelt werden kann. Zum anderen haben die untersuchten Fragen einen direkten Bezug zu Anwendungsgebieten wie Bildverarbeitung, Computergraphik, Geographische Informationssysteme und Robotik.

Dieses Lehrbuch gibt eine Einführung in häufig verwendete algorithmische Techniken wie Sweep, Divide-and-Conquer, randomisierte inkrementelle Konstruktion, Dynamisierung, amortisierte Kostenanalyse und kompetitive Analyse. Es stellt wichtige geometrische Strukturen vor wie konvexe Hülle, Voronoi-Diagramm und Delaunay-Triangulation sowie höherdimensionale Datenstrukturen.

Das Buch beruht auf Vorlesungen, die der Verfasser seit 12 Jahren an verschiedenen Universitäten gehalten hat. Die vorliegende zweite Auflage wurde gründlich überarbeitet. Sie enthält über 220 Abbildungen und über 60 Übungsaufgaben leichten bis mittleren Schwierigkeitsgrades mit Lösungen. Zusätzlich bietet ein Geometrie-Labor mit interaktiven Java-Applets die Möglichkeit, mit geometrischen Strukturen und Algorithmen zu experimentieren