אסתר ארקין

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

ביוגרפיה

גדלה בתל אביב, ולמדה בתיכון עירוני י"ד.

ב-1981 ארקין השלימה לימודי תואר ראשון במתמטיקה באוניברסיטת תל אביב. המשיכה את לימודיה באוניברסיטת סטנפורד, שם סיימה לימודי תואר שני בחקר ביצועים ב-1983 ודוקטורט ב-1986. תזת הדוקטורט שלה, Complexity of Cycle and Path Problems in Graph, נכתבה בהנחיית כריסטוס פאפאדימיטריו.

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

ב-1995 עבדה מספר חודשים באוניברסיטת תל אביב כפרופסור חבר אורחת.

החל מ-1991 ארקין חברת סגל הפקולטה למתמטיקה יישומית וסטטיסטיקה באוניברסיטת סטוני ברוק.

חיים אישיים

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

ממחקריה

בעיות תזמון של בירורקרט עצלן

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

המאמר ממחיש את הבעיה עם הדוגמה הבאה:

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

מדד להשוואת מצולעים

ארקין ושותפים פיתחו מדד להשוואת מצולעים, בדרך שנחשבת יעילה לחישוב. המדד פורסם במאמר מ-1989 הנקרא An efficiently computable metric for comparing polygonal shapes (מדד יעיל-לחישוב להשוואת מצולעים). המאמר הוא מאמרה המצוטט ביותר של ארקין, עם מעל ל-1,000 ציטוטים (נכון לנובמבר 2023). המאמר ממשיך להיות מצוטט גם כ-25 שנים לאחר פרסומו המקורי.

המדד משמש לחיפוש תמונות, מערכות ראיה ממוחשבת, מערכות מידע גאוגרפי ועוד.

המדד

קובץ:Turn function.png

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

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

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

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

לאחר יצירת הפונקציה התואמת למצולע, ניתן להשתמש בכלים מתמטיים מוכרים להשוואת פונקציות. ארקין ושותפיה בחרו להשתמש במטריקת $L^p$.

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

• תבנית:קישור כללי