גאומטריה חישובית

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש
הקְמוֹר של אוסף של נקודות במישור הדו-ממדי (בכחול). ניתן לחשוב על הקמור כעל גומייה שנמתחה כך שתקיף את כל הנקודות, ולאחר מכן שוחררה.

גאומטריה חישובית היא תחום במתמטיקה ובמדעי המחשב העוסק במבני נתונים ובאלגוריתמים לפתרון בעיות גאומטריות באמצעות מחשב. הבעיות הנדונות בתחום זה נוגעות לעצמים גאומטריים כמו נקודות, קטעים ומצולעים במישור, או לנקודות, לקטעים, למשטחים וכדומה במרחב מממד גבוה יותר. המחקר העיוני בגאומטריה חישובית מיושם בתחומים אחרים במדעי המחשב, כגון: ראייה ממוחשבת, גרפיקה ממוחשבת, רובוטיקה ומערכות תיב"ם וכן בתחומים שאינם נמנים עם מדעי המחשב, כגון: הנדסה, סטטיסטיקה, מערכת מידע גאוגרפית וביולוגיה מולקולרית.

נושאים נוספים

  • בעיית הגלריה לאמנות העוסקת במספר הקטן ביותר של שומרים בגלריה כך שיוכלו מבלי לעזוב את משמרתם להשגיח על כל נקודה בגלריה שקירותיה ישרים.
  • הסריקה של גראהם שהוא אלגוריתם למציאת הקמור של קבוצת נקודות במישור.
  • שילוש דלוני של קבוצת נקודות במישור הוא שילוש של קבוצת הנקודות כך שאף נקודה אינה נמצאת בתור המעגל החוסם אחד מהמשולשים. התכונה אחרונה גורמת לשילוש להיות אופטימלי, מבחינות מסוימות, משום שהיא מבטיחה שהמשולשים שירכיבו את השילוש יהיו עבים ושמנים, ולא ארוכים ודקים.


P Computer-science.svg ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום למכלול ולהרחיב אותו.