Efficient Enumeration and Minimal Area of Totally Concave Polyominoes
Researchers present findings on total concavity in polyominoes, exploring the minimal area, efficient enumeration methods, and asymptotic behaviors. Various bounds and algorithms are discussed, including a backtracking prototype and Jensen's algorithm for counting polyominoes without generating all possibilities.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
On Totally Concave Polyominoes Minimal Area, Efficient Enumeration, and Asymptotics Gill Barequet, Noga Keren and Adi Rivkin Technion IIT Johann Peters Univ. of Waterloo EuroCG - 2024
Polyomino An edge-wise connected collection of cells on the square lattice. Polyomino s bounding box smallest surrounding rectangle. EuroCG - 2024
Total Concavity Total concavity jump in every row and column. What is the smallest TCP? How can TCPs be efficiently counted? EuroCG - 2024
What is the smallest TCP? EuroCG - 2024
Minimal Area of TCPs Consider a TCP of area ? in a (?,?) bounding box. Obtain the following relations: (1) Lower bound: ? 2? + 2? 1 (2) Upper bound (WLOG, ? ?): ? ?? (? + 2) EuroCG - 2024
Combining UB and LB By case analysis, the minimal values: ?,? = 5,6 ? 21 ? = 21 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 EuroCG - 2024
How can TCPs be efficiently counted? EuroCG - 2024
Prototype Backtracking Algorithm Notation: ? ? = #???(?) Recursively concatenate concave columns ?(?) up to ? = 26 Python 12GB RAM 90 hours EuroCG - 2024
Jensens Algorithm (Jensen, 2001) Counts polyominoes without generating all possible polyominoes Tracks only right boundaries of the polyominoes Left to right, top to bottom EuroCG - 2024
Jensens Algorithm (Jensen, 2001) Consisted of signatures Occupied cells (boundary) Connectivity components Two bits specify whether the polyomino touched top and bottom strips Maintains a dictionary database of signatures : #polyominoes EuroCG - 2024
Jensens Algorithm Totally Concave Case Consisted of signatures Occupied cells (boundary) Connectivity components Two bits specify whether the polyomino touched top and bottom strips TC state of each row 0 1 2 3 EuroCG - 2024
Jensens Algorithm Totally Concave Case Consisted of signatures Occupied cells (boundary) Connectivity components Two bits specify whether the polyomino touched top and bottom strips TC state of each row 0 1 2 3 EuroCG - 2024
Results Jensen (TC Case) ?(?) up to ? = 35 C++ 128GiB RAM 41 hours EuroCG - 2024
Growth Constant of ?(?) ?? ? Growth constant of ?(?): ? lim ? ?? ? Growth constant of ?(?): ?? lim ? Results: Existence and finiteness of ?? Lower bound EuroCG - 2024
Composition and Concatenation Composition A relative placement. Lexicographic order Left to right, bottom to top. Concatenation A lexicographic composition. ?2 ?1 EuroCG - 2024
??Existence and Finiteness Concatenation of TCPs: ? ? ? ? ? ? + ? Exponential upper bound: ? ? ?? By a lemma of Fekete: ?? ? exists and is finite. ?? ??? ? EuroCG - 2024
TCP Lexicographic Compositions TCPs have at least 4 lexicographic compositions: EuroCG - 2024
Lower Bound on ?? Lexicographic compositions: 2 ? 2? 4 ? ? 1 ?is a lower bound on ??. Any 4? ? Best lower bound (? = 35): 1 35> 2.4474 ?? 4? 35 EuroCG - 2024
Efficiency Analysis Jensen (TC Case) ?(?) = ?? Lower bound: ??> 2.4474 ? EuroCG - 2024
Efficiency Analysis Jensen (TC Case) Empirically shown: #???(?) is O(2.2?) Algorithm is O 2.2?< 2.4?< ?? More efficient than any algorithm which generates all TCPs! ?= ?(?) EuroCG - 2024
Thanks for your attention! EuroCG - 2024
