הצגת המקור של הדף "קמור"

[[קובץ:ConvexHull.svg|200px|שמאל|ממוזער|הקְמוֹר של אוסף של נקודות במישור הדו-ממדי תחום על ידי הקו הכחול. ניתן לחשוב על הקמור כתחום על ידי גומייה שנמתחה כך שתקיף את כול הנקודות, ולאחר מכן שוחררה.]]
[[קובץ:Vitruvian Man's convex hull.jpg|200px|שמאל|ממוזער|הקמור של [[האדם הוויטרובי]]. התמונה ממחישה את ההבדל בין מושג ה[[צורה חסומה|חסימה]] למושג הקמור. הריבוע חוסם את הדמות עם הרגליים הצמודות, ה[[מעגל חוסם]] את הדמות עם הרגליים הפשוקות, והצורה המסומנת בקו אדום היא הקמור של שתי הדמויות כאחד.]]
ב[[מתמטיקה]], ה'''קְמוֹר'''{{הערה|{{מילון אקדמיה|138|57501_1|קְמוֹר}}}} של גוף, או של אוסף של גופים, הוא ה[[גוף קמור|גוף הקמור]] המינימלי המכיל אותם. במקרה הפרטי, שבו אוסף הגופים הוא אוסף של [[נקודה (גאומטריה)|נקודות]], [[עקומה|עקומות]] ו[[צורה גאומטרית|צורות דו-ממדיות]], ב[[מישור (גאומטריה)|מישור]] הדו-ממדי, ניתן לדמות את הקמור לשטח שתחום על ידי גומייה, שנמתחה כך שתקיף את כולם, ולאחר מכן שוחררה. המקבילה של הגומיה ב[[מרחב תלת-ממדי|מרחב התלת-ממדי]], היא יריעה אלסטית מתוחה, שמקיפה אוסף של עצמים גאומטריים. הקמור של אוסף נקודות, [[קטע (גאומטריה)|קטעים]] ו[[מצולע|מצולעים]] במישור, הוא [[מצולע]]. הקמור של אוסף נקודות, קטעים, מצולעים ו[[פאון|פאונים]] במרחב התלת-ממדי, הוא פאון.

== הגדרה מתמטית ==
בהינתן [[מרחב וקטורי]] <math>V</math> מעל [[שדה המספרים הממשיים|שדה הממשיים]] <math>\mathbb{R}</math> וקבוצה כלשהי <math>B \subseteq V</math>, ה'''קמור של <math>B</math>''' מוגדר להיות:

<math>
\operatorname{Con}(B):=\bigcap_{\begin{matrix} B\subseteq C \subseteq V \\ C\text{ is convex} \end{matrix}}{C}</math>

כלומר, [[חיתוך (מתמטיקה)|חיתוך]] כל הקבוצות הקמורות המכילות את <math>B</math>. חיתוך זה [[מוגדר היטב]] לכל <math>B</math> מכיוון שהמרחב הווקטורי <math>V</math> עצמו הוא קבוצה קמורה, ולכן החיתוך מכיל איבר אחד לפחות.

ניתן להוכיח כי ההגדרה לעיל שקולה לאוסף כל ה[[צירוף ליניארי|צירופים הליניאריים]] של איברים מ-<math>B</math> עם מקדמים [[מספרים חיוביים ושליליים|חיוביים]] שסכומם הוא 1. כלומר, אוסף כל הווקטורים <math>a_1v_1+a_2v_2+\dots a_nv_n</math> כך ש:

* <math>n \in \mathbb{N}</math> [[מספר טבעי]]
* <math>v_i\in B</math> לכל <math>1\le i \le n</math>
* <math>0<a_i</math> לכל <math>1\le i \le n</math>
* <math>\sum_{i=1}^n{a_i}=1</math>

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

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

==ראו גם==
* [[קבוצה קמורה]]

==קישורים חיצוניים==
* [http://www.cs.princeton.edu/courses/archive/fall08/cos226/demo/ah/ConvexHull.htm הסבר והמחשת קמור (באנגלית).]{{קישור שבור|date=יולי 2020 |bot=InternetArchiveBot |fix-attempted=yes }} למטה יש קישורים למימושים ממוחשבים שונים, כולל זה הנמצא כאן למטה.
* [http://www.cs.princeton.edu/courses/archive/fall08/cos226/demo/ah/GrahamScan.html הדגמה של קמור של קבוצת נקודות במישור]
* {{MathWorld}}

==הערות שוליים==
{{הערות שוליים}}

[[קטגוריה:גאומטריה]]
[[קטגוריה:גאומטריה חישובית]]
[[קטגוריה:קמירות]]