שיחה:קמור

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

אתה צודק, אפשר לפרט טיפה יותר כאן. באופן כללי, אלגוריתם שאין לו שום מידע נוסף על הקלט יהיה חייב לבצע השוואות (כי הן הדבר היחיד שמספק מידע על הקלט), ולכן החסם יהיה תקף לגביו. לכן גם כתוב בערך "במקרה הכללי". גדי אלכסנדרוביץ' 05:32, 11 ינואר 2006 (UTC)

גם במקרה הכללי יש אלגוריתם שמוצא קמור ב O(nh) כאשר n זה מספר הנקודות הכולל ו h זה מספר הנקודות בקמור. אני לא יודע למה בטכניון מלמדים את החסם שציינת. אלגוריתם Gift Wrap סיבוכיות O(nh)

אני די מתפלא על עצמי שלא הזכרתי גם את האלגוריתם הזה, אבל כמובן שהוא לא משנה הרבה: במקרה הגרוע ביותר הסיבוכיות שלו תהיה ריבועית אם כל הנקודות נמצאות על הקמור (כמו במקרה של המיון). מה שכן, כדאי לפרט כאן קצת על כך שאפשר למצוא את הקמור של כל עקום פוליגונלי פשוט שכבר נתון לנו בזמן לינארי, ואפשר לדבר גם על קמורים רב ממדיים. בקיצור, יש מה להרחיב, אין מה לקצץ. גדי אלכסנדרוביץ' 08:29, 20 מאי 2006 (IDT)