דלג לתוכן (מקש קיצור 's')
אירועים

אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

event speaker icon
גיל בן-שחר (הרצאה סמינריונית למגיסטר)
event date icon
יום שלישי, 26.06.2018, 10:30
event location icon
Taub 601
event speaker icon
מנחה: Prof. G. Barequet
A polyomino is an edge-connected set of cells on the square lattice. The problem of counting poyominoes dates back to the 1950s when it was studied in parallel in the fields of combinatorics and statistical physics. The study of polyominoes usually classifies polyominoes by their area, which is the number of cells the polyomino contains. Less explored is the perimeter of a polyomino, which is the set of empty cells adjacent to the polyomino. Several works studied the relation between the area of a polyomino and its perimeter. In this work we study the combinatoric and geometric properties of a special class of polyominoes, namely minimal-perimeter polyominoes, which, as the name suggests, are polyominoes with minimal perimeter for their area. In this talk we will present proofs for some geometric properties of minimal-perimeter polyominoes, which in turn, yield proofs of the combinatorial structure of minimal-perimeter polyominoes. In addition, these properties, allow us to devise efficient algorithms for counting the number of minimal-perimeter polyominoes.