מרחק צ'בישב

מרחק צ'בישב (או מטריקת מקסימום או מטריקת $L_{\infty }$) הוא מטריקה המוגדרת על מרחב וקטורי בו המרחק בין שני וקטורים הוא ההפרש המקסימלי המתקבל בין הקואורדינטות שלהם בממדים השונים. הוא קרוי על-שם פפנוטי צ'בישב.

מרחק צ'בישב גם ידוע כמרחק השחמט: הוא שווה למספר הצעדים המינימלי שהמלך עושה בלוח שחמט כדי להגיע למשבצת כלשהי (המלך יכול לנוע אופקית, אנכית ובאלכסון). למשל המרחק בין ו5 ל ו1 או ב1 הוא: 4.

8 7 6 5 4 3 2 1 א ב ג ד ה ו ז ח

במטריקה זו, מעגל ברדיוס $r$, הוא קבוצת הנקודות עם מרחק צ'בישב $r$ מנקודת המרכז. צורת המעגל כאן היא ריבוע שצלעותיו באורך $2r$ והן מקבילות למערכת הצירים של הקואורדינטות. בלוח שחמט בו נעשה שימוש במרחק צ'בישב דיסקרטי ולא רציף, מעגל עם רדיוס $r$ הוא ריבוע שצלעו $2r$ (יש למדוד ממרכז המשבצת למרכז המשבצת ולא את המשבצות עצמן). מספר המשבצות בכל צלע הוא $2r+1$. למשל עיגול עם רדיוס 1 בלוח שחמט יהיה ריבוע עם $3\times 3$ משבצות.

הגדרה

מרחק צ'בישב בין שני וקטורים או נקודות $p$ ו-$q$ עם קואורדינטות $p_{i}$ ו-$q_{i}$ בהתאמה הוא:

$D_{\rm {Chebyshev}}(p,q):=\max _{i}(|p_{i}-q_{i}|).\$

בשני ממדים, כלומר בגאומטרית המישור, אם לנקודות $p$ ו-$q$ יש קואורדינטות קרטזיות $(x_{1},y_{1})$ ו-$(x_{2},y_{2})$ אז מרחק צ'בישב שלהן הוא:

$D_{\rm {Chess}}=\max \left(\left|x_{2}-x_{1}\right|,\left|y_{2}-y_{1}\right|\right).$

השוואה בין מטריקות מרחק צ'בישב ומרחק מנהטן

במימד אחד, כל המטריקות שווה היות שהן הערך המוחלט של ההפרש.

בשני ממדים קיימת שקילות בין מרחק צ'בישב למרחק מנהטן:

• בשניהם צורת המעגל היא ריבוע.
• במרחק צ'בישב הריבוע מקביל לצירי הקואורדינטות ובמרחק מנהטן הוא בזווית $\pi /4$ ‏(45°) אליהן.
• אורך הצלע שונה: במרחק צ'בישב הוא $2r$ ואילו במרחק מנהטן ${\sqrt {2}}r$.

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

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

שימושים

מרחק צ'בישב משמש בלוגיסטיקה של מחסנים היות שהוא מודד היטב את הזמן הנדרש לעגורן גשר להעביר חפצים מנקודה לנקודה. העגורן יכול לנוע בציר ה-x או בציר ה-y או באלכסון אך בכל המקרים מהירותו זהה.

על רשת (כמו לוח השחמט) הנקודות הנמצאות במרחק צ'בישב 1 מנקודה נתונה מהווים את סביבת מור של אותה נקודה.

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

• מרחק צ'בישב, באתר MathWorld (באנגלית)