Depois de ouvir Emo Welzl falar sobre o assunto neste verão, eu sei que o número de triangulações de um conjunto de pontos no avião está entre cerca de e . Desculpas se estou desatualizado; atualizações bem-vindas.
Eu mencionei isso na aula e queria acompanhar com breves observações sábias para dar aos alunos uma idéia de (a) por que se mostrou tão difícil determinar essa quantidade e (b) por que tantos se importam em defini-la. Descobri que não tinha respostas adequadas para esclarecer qualquer questão; muito pela minha sagacidade!
Eu apreciaria sua opinião sobre essas questões reconhecidamente vagas. Obrigado!
co.combinatorics
cg.comp-geom
Joseph O'Rourke
fonte
fonte
Respostas:
Aqui está mais uma razão "aplicada" por que nos preocupamos com triangulações. Há um corpo de trabalho sobre compressão de malha em que o objetivo é usar o mínimo de bits por vértice possível para codificar uma malha (principalmente para ajudar no armazenamento e na transmissão). A base específica do expoente no número de triangulações de um conjunto de pontos planares fornece um limite inferior teórico da informação ao número de bits necessários por vértice (especificamente, triangulações significa que você precisa de pelo menos 8,48 bits por vértice). Tais limites podem então ser comparados com os esquemas de compressão de malha reais para determinar sua eficácia.8.48n
fonte
O limite inferior havia sido ligeiramente aprimorado para ( consulte o arXiv aqui ). Tento manter limites atualizados para várias variantes deste problema nesta página da Web (desculpe-me por este auto-anúncio descarado).8.6 ( 8,65n)
Gosto muito da sua afirmação de que o problema é difícil porque "entender a não cruzar é difícil". O limite de (e alguns dos limites anteriores) depende de uma conexão entre o número de triangulações e as propriedades esperadas de uma triangulação aleatória (escolhida uniformemente no conjunto de todas as triangulações possíveis do conjunto de pontos). Isso transforma o problema no estudo das propriedades esperadas de uma triangulação aleatória, o que é difícil, porque a não cruzagem não nos permite usar as ferramentas probabilísticas padrão (por exemplo, não podemos escolher cada aresta com alguma probabilidade pois isso pode induzir alguns cruzamentos ) Portanto, a não-travessia nos obriga a desenvolver novos métodos para estudar gráficos aleatórios.30n p
fonte