קמור

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

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

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

הגדרה מתמטית

בהינתן מרחב וקטורי $V$ מעל שדה הממשיים $\mathbb {R}$ וקבוצה כלשהי $B\subseteq V$, הקמור של $B$ מוגדר להיות:

$\operatorname {Con} (B):=\bigcap _{\begin{matrix}B\subseteq C\subseteq V\\C{\text{ is convex}}\end{matrix}}{C}$

כלומר, חיתוך כל הקבוצות הקמורות המכילות את $B$. חיתוך זה מוגדר היטב לכל $B$ מכיוון שהמרחב הווקטורי $V$ עצמו הוא קבוצה קמורה, ולכן החיתוך מכיל איבר אחד לפחות.

ניתן להוכיח כי ההגדרה לעיל שקולה לאוסף כל הצירופים הליניאריים של איברים מ-$B$ עם מקדמים חיוביים שסכומם הוא 1. כלומר, אוסף כל הווקטורים $a_{1}v_{1}+a_{2}v_{2}+\dots a_{n}v_{n}$ כך ש:

• $n\in \mathbb {N}$ מספר טבעי
• $v_{i}\in B$ לכל $1\leq i\leq n$
• $0<a_{i}$ לכל $1\leq i\leq n$
• $\sum _{i=1}^{n}{a_{i}}=1$

אלגוריתמי חישוב הקמור

חישוב הקמור הוא בעיה בגאומטריה חישובית. ישנם מספר אלגוריתמים העוסקים בחישוב זה, הן במקרים המיוחדים של שניים ושלושה ממדים, והן במקרה של מספר ממדים כלשהו. שני אלגוריתמים ידועים למציאת קמור של אוסף נקודות במישור הדו־ממדי הם הסריקה של גראהם והצעדה של ג'ארביס. החסם התחתון על זמן מציאת הקמור של אוסף בן $\ n$ נקודות במקרה הגרוע הוא $\ n\log n$. ניתן להצדיק חסם זה על ידי כך שבאמצעות אלגוריתם שמוצא קמור ניתן למיין סדרת נקודות, והוכח כי מיון חסום מלמטה במקרה הכללי (בו אין מידע נוסף על האלמנטים הממוינים) על ידי $\ n\log n$. עבור מרחב מממד $\ d>3$ החסם התחתון הוא $\ n^{\left[d/2\right]}$ בשל סיבוכיות הפאון שייווצר.

מקור השם

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

ראו גם

• קבוצה קמורה

קישורים חיצוניים

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