What type of study is this?

This is a Quantitative Study study.

October 17, 2025RAIRO - Theoretical Informatics and Applications0 citationsOpen Access

Contagem eficiente de polióminos k-convexos

AGA J GuttmannThe University of Melbourne PMPaolo MassazzaUniversity of Insubria

Key Points

O número de polióminos k-convexos pode ser contado de forma eficiente com base na área.
O método proposto opera em tempo polinomial com uma complexidade de espaço de O(n^4).
A abordagem foca no grau de convexidade, destacando as mudanças de direção na estrutura.
Este trabalho estende técnicas de contagem para polióminos convexos, fornecendo novas percepções sobre geometria combinatória.

Abstract

O grau de convexidade de um poliómino convexo P é o menor inteiro k tal que quaisquer duas células de P podem ser unidas por um caminho monotônico dentro de P com no máximo k mudanças de direção. Neste artigo, mostramos que, para qualquer inteiro fixo k > 2, o número de polióminos de área n e grau de convexidade no máximo k pode ser calculado em tempo polinomial usando O(n^4) espaço.

Perguntar à IA

Bookmark

View Full Paper