ריצוף של המישור

ריצוף הוא כיסוי של משטח או קבוצה כללית יותר באריחים מאותו סוג.

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

ריצופים באמנות

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

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

ריצופים בטבע

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

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

יצירת ריצופים מורכבים על בסיס ריצופים פשוטים

בתמונה מופיע הסבר כיצד על בסיס של ריצופים פשוטים ניתן לבנות ריצופים מסובכים יותר, כגון אלו שאשר השתמש בהם בציוריו. ההתחלה היא מאריח פשוט המרצף את המישור, לדוגמה: ריבוע (משבצת 1). עתה גוזרים מהצלע העליונה שלו צורה כלשהי (משבצת 2), ומדביקים אותה על הצלע התחתונה (משבצת 3). מבצעים אותה פעולה על הצלעות הימנית והשמאלית (משבצות 4,5), ולבסוף מתקבל באופן זה האריח הנראה במשבצת 6. באותו אופן ניתן לבנות ריצוף מורכב יותר באמצעות האריח החדש (משבצת 7). ניתן להשיג גם סימטריה שונה על ידי סיבוב והדבקה על הצלע הימנית.

ריצופים בעזרת מצולעים משוכללים

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

ריצופים משוכללים

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

ריצוף באמצעות משולשים
ריצוף באמצעות ריבועים
ריצוף באמצעות משושים

ריצופים אוניפורמיים

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

Snub Hexagonal Tiling
Trihexagonal Tiling
Elongated Triangular Tiling
Snub Square Tiling
Small Rhombitrihexagonal Tiling
Truncated Square Tiling
Truncated Hexagonal Tiling
Great Rhombitrihexagonal Tiling

סימטריות של ריצופים

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

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

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

החבורה p1: אין סימטריות אחרות למעט הזזות
החבורה p2: מכילה סימטריות להזזה וכן לסיבוב ב-180 מעלות. (התמונה לקוחה משטיח מצרי)
החבורה pm: עבורה קיימת גם סימטריה לשיקוף בציר אחד
החבורה pg: עבורה קיימים גלישה-שיקוף אך לא קיימת סימטריה לסיבובים או שיקופים.
החבורה pmm: קיימים שיקופים בשני צירים ניצבים וכן 4 מרכזים לסיבובים ב-180 מעלות (הצילום הוא של גדר עץ בארצות הברית)
החבורה pmg: קיימים שני צירים של סיבוב ב-180 מעלות, ציר שיקוף אחד וציר אחד של גלישה-שיקוף (הצילום הוא של רקמה מהוואי)
החבורה pgg: שני צירים לסיבוב ב- 180 מעלות וכן שני צירים אנכיים של גלישה-שיקוף (הצילום הוא של מדרכה בבודפשט)
החבורה cmm: מכילה שיקופים בשני צירים שונים וכן סיבובים ב- 180 מעלות (הצילום הוא של קיר לבנים)
החבורה p4: בחבורה זאת שני מרכזים לסיבובים ב-90 מעלות ומרכז אחד לסיבובים ב-180 מעלות. (הצילום הוא של תקרת קבר מצרי)
החבורה p4m: קיימים שני מרכזים לסיבובים בכפולות של 90 מעלות וכן ארבעה צירים לשיקופים
החבורה p4g: קיימים שני מרכזים לסיבובים בכפולות של 90 מעלות אך רק שני צירים לשיקופים וכן שני צירים לשיקוף-גלישה (הצילום הוא של פורצלן סיני)
החבורה p3: מכילה שלושה מרכזים לסיבובים בכפולות של 120, אבל לא מכילה שיקופים או שיקוף גלישה (הצילום הוא של ציור קיר מאלהמברה בספרד)
החבורה p3m1: מכילה 3 צירים לשיקופים, 3 מרכזים לסיבובים בכפולות של 120 מעלות שכל אחד מהם נמצא על ציר שיקוף ו-3 צירים של שיקוף-גלישה
החבורה p31m: כמו החבורה הקודמת היא מכילה שלושה מרכזים לסיבובים מסדר שלישי (כפולות של 120 מעלות), ושלושה צירים של שיקופים אבל המרכז של לפחות אחד הסיבובים לא נמצא על ציר שיקוף. כמו כן ישנם שלושה צירים של שיקוף-גלישה (הצילום הוא של פורצלן סיני)
החבורה p6: מכילה סיבובים בכפולות של 60 מעלות בלבד (בתמונה קישוט פרסי)
החבורה p6m: מכילה סיבובים בכפולות של 60 וכן שיקופים ב-6 צירים (בתמונה ריצוף פרסי)

ריצוף באמצעות מצולעים קמורים

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

בשנת 1968 נראה היה שהבעיה נפתרה, מכיוון שהמתמטיקאי ריצ'רד קרשנר טען בעבודת הדוקטורט שלו שהצליח לסווג את כל סוגי המחומשים והמשושים בעזרתם ניתן לרצף את המישור. עד לשנת 1968 היו ידועים רק 5 סוגים שונים של מחומשים כאלו וקרשנר הצליח למצוא 3 סוגים נוספים וכן "להוכיח" שאלו כל סוגי המחומשים האפשריים. בשנת 1975 פרסם מרטין גרדנר בטור הידוע שלו בסיינטיפיק אמריקן מאמר על בעיה זו, יחד עם התוצאות של קרשנר. אחד מקוראיו של גרדנר, מתכנת מחשבים בשם ריצ'רד ג'יימס השלישי, החליט לחפש אחר פתרון לחידה מבלי לקרוא את הפתרונות של קרשנר. הוא אכן הצליח למצוא מחומש המרצף את המישור ולהפתעתו המחומש לא נכלל ב-8 הסוגים שתוארו על ידי קרשנר. מכאן, שבהוכחה של קרשנר נפלה טעות והבעיה נפתחה מחדש. הנושא הצית את דמיונה של מרג'ורי רייס (Marjorie Rice), עקרת בית מפלורידה, שמצאה בריצופים שילוב בין אהבתה למתמטיקה ואהבתה לאמנות. רייס החלה לחקור בצורה שיטתית את סוגי הריצופים שפורסמו ולחפש אחר חדשים, ולצורך כך פיתחה לעצמה מעין אלגברה מיוחדת משלה. המאמצים שלה נשאו פרי ועד לשנת 1977 היא הצליחה למצוא 3 סוגים נוספים של מחומשים איתם ניתן לרצף את המישור וכן 60 סוגים של ריצופים בעזרת מחומשים שלא היו ידועים קודם לכן. בשנת 1985, סטודנט גרמני בשם רולף שטיין מצא סוג נוסף של מחומש המרצף את המישור, בשנת 2015 מצאו שלושה מתמטיקאים (Mann/McLoud/Von Derau) מאוניברסיטת וושינגטון בבות'אל סוג נוסף של מחומש. בסך הכל ידועים 15 סוגים של מחומשים קמורים שבאפשרותם לרצף את המישור.

ריצופים לא מחזוריים

בעיות החלטה ואריחי ואנג

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

בשנת 1966 הצליח רוברט ברגר (Robert Berger) למצוא סט שמכיל 20,426 אריחי ואנג. בהמשך הצליח ברגר לצמצם את מספר האריחים ל-104, והנס לוֹיכלי (Hans Läuchli) הצליח להוריד את המספר ל-40. בשנת 1971 הצליח רפאל רובינסון (Raphael M. Robinson) ליצור סט אריחי ואנג המכיל רק 6 אריחים. פרט להפרכת השערתו של ואנג, ברגר ורובינסון גם הציגו הוכחה לכך שלא קיים אלגוריתם מהסוג המבוקש - כלומר, בעיית הדומינו היא בעיה לא כריעה. ההוכחה מתבססת על ביצוע סימולציה של ריצת מכונת טיורינג באמצעות אריחי ואנג והתבססות על אי כריעות בעיית העצירה. בכך מודגם שבעיות ריצוף "מסתירות" בתוכן מודל חישובי לא טריוויאלי. בשנת 1973 חלה התקדמות גדולה כאשר הפיזיקאי רוג'ר פנרוז מצא 3 סטים נוספים של אריחים כאלו, כך שבכל סט ישנם שני אריחים בלבד. בשנת 1977 פרסם רוברט אמן (Robert Ammann) כמה סטים נוספים.

ריצוף פנרוז וגבישים כמו-מחזוריים

כאמור, ריצופי פנרוז (Penrose tiling) התגלו על ידיי רוג'ר פנרוז בשנת 1973, ולמעשה הוא גילה מספר זוגות של אריחים כאלו בעזרתם ניתן לרצף את המישור אך לא בצורה מחזורית. בתמונות למטה ניתן למצוא את שני הזוגות המפורסמים ביותר, זוג המעוינים והזוג הקרוי "העפיפון והחץ". פנרוז סיפר שההשראה לריצופים האלו באה מתוך קריאת הספר Harmonis Mondis של יוהנס קפלר, שעסק בין היתר גם בריצופים.

אריחי פנרוז המבוססים על מעוינים
ריצוף שנבנה באמצעות אריחי פנרוז המעוינים
ריצוף 'כוכב' באמצעות אריחי פנרוז
העפיפון והחץ.

ריצוף הכוכב מראה כמה מהתכונות המרתקות של ריצופי פנרוז. ראשית ניתן לראות שלריצוף יש תכונה של "דמיון עצמי" - ניתן לבנות בעזרתו עותקים גדולים יותר ויותר של הכוכב. בנוסף לריצוף יש סימטריה לסיבובים מסדר חמישי, סיבובים ב 360/5=72 מעלות.

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

ריצוף ספירלי

ספירלה יכולה לרצף את המישור, עם חלקים אשר זהים זה לזה או עם חלקים הולכים וגדלים^[1]. המקרה הראשון מודגם באמצעות ריצוף וודרברג, שגילה האנס וודרברג (Voderberg) בשנת 1936, וניתן גם למצוא דוגמאות שלו בטבע, באבקני פרחים למשל.

המקרה השני של ריצוף ספירלי הוא חלקים דומים זה לזה אך הולכים וגדלים, ריצוף מסוג זה נקרא ריצוף ספירלי לוגריתמי. דוגמאות לריצוף לוגריתמי ניתן למצוא בטבע, בקונכיית הנאוטילוס, כמו גם בריצופים מעשה אדם.^[2] הגודל של כל אריח גדול מקודמו פי מספר קבוע, כך שהגדלים נתונים על סולם לוגריתמי ומכאן השם. ניתן להחשיב ריצוף ספירלי לוגריתמי גם כסוג של ריצוף בעל דמיון עצמי.

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

דמיון עצמי, פרקטלים וריצופים

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

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

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

הכללות

אומרים שקבוצה חסומה ומדידה X מרצפת בהזזות את המרחב האוקלידי, אם קיימת קבוצה (דיסקרטית) L כך שכמעט כל נקודה מופיעה בדיוק באחת ההזזות $X+\lambda$ (עבור $\lambda \in L$ ). לתכונה זו יש קשר חזק לקיומו של בסיס אורתונורמלי של פונקציות אקספוננציאליות למרחב הפונקציות $\ L^{2}(X)$ , שהוביל להשערת פוגליד (אנ'), לפיה קבוצה X מרצפת את המרחב האוקלידי (בהזזות) אם ורק אם יש למרחב הפונקציות שלה בסיס כנ"ל. השערה זו הופרכה ב-2004 על ידי טרנס טאו בממד 5 ומעלה (ואחר-כך גם בממדים 3 ו-4). כל גוף קמור המרצף את המרחב האוקלידי הוא פאון. אומרים שפאון הוא סימטרי לשיקוף אם הוא סימטרי ביחס לשיקוף סביב מרכז הכובד שלו. פאון קמור מרצף את המרחב (בהזזות) אם ורק אם (1) הוא סימטרי לשיקוף, (2) כל דופן שלו (כלומר פאה מקו-ממד 1) סימטרית לשיקוף, ו-(3) בכל מחלקת הזזה של פאה מקו-ממד 2 יש בדיוק 4 או 6 פאות (McMullen, 1980). בפרט, הפאונים הקמורים המרצפים (בהזזות) את המישור הם (עד כדי העתקה אפינית) המקבילית והמשושה הסימטרי בלבד; יש 6 פאונים קמורים המרצפים (בהזזות) את המרחב התלת-ממדי; ו-52 המרצפים (בהזזות) את המרחב ה-4 ממדי.

לריצופים יש חשיבות רבה בגאומטריה (ובטופולוגיה אלגברית), בכך שהם מאפשרים ללמוד את הקבוצה המכוסה X על ידי תכונות של הכיסוי. לכיסוי משויכת חבורה G. במקרה שהחבורה פועלת באופן טרנזיטיבי, האריחים בהכרח חופפים זה לזה, ואפשר להתאים ביניהם לבין מרחב המנה $\ X/G$ . קשרים אלה הם נקודת המוצא של תוכניתו של פליקס קליין מסוף המאה ה-19, ללמוד מרחבים גאומטריים דרך החבורות הפועלות עליהם, ולהפך.

שעשועי מתמטיקה הקשורים בריצופים

פוליאומינו

ערך מורחב – פוליאומינו

בשנת 1953 הציג סולומון גולומב (Solomon W. Golomb) את המונח פוליאומינו (polyomino), המתאר "יצורים" (שלעיתים מכונים "Lattice Animals") המורכבים מחיבור של מספר ריבועים זה לזה (לאורך שפתיהם). הפוליאומינו מחולקים למשפחות לפי מספר הריבועים שהיצורים מכילים: המונומינו מכיל ריבוע אחד, הדומינו בנוי משני ריבועים, הטרומינו משלושה (וישנם שני יצורים במשפחת הטרומינוים) הטטרומינו בנויים מארבעה ריבועים (וישנם 5 יצורים שונים כאלו, המככבים, יחד עם שיקופים שלהם, במשחק הטטריס) וכך הלאה. בעקבות המצאת הפוליאומינו החל להיווצר גל גדול של חידות הקשורות אליהן ורובם קשורות לריצופים בעזרת הפוליאומינו. החידה המפורסמת ביותר בהקשר זה היא האם ניתן לרצף לוח שחמט 8x8 שממנו הורידו את שתי הפינות הנגדיות, בעזרת חתיכות של דומינו בלבד. שאלה שסביבה יש שעשועים אלו צורות מתוך הפוליאומינו מסוגלים לרצף את המישור כולו? חידות נוספות נוגעות לריצופים של צורות ספציפיות לדוגמה כיצד ניתן לרצף מלבן בגודל 6x10 בעזרת 12 צורות הפנטומינו?

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