[pt] A tecnologia multitoque vem se configurando nos últimos anos como tendência. As interfaces multitoque permitem interagir com um objeto virtual diretamente, de maneira parecida com um objeto real. Porém, esta tecnologia não tem só vantagens. Há várias questões a serem resolvidas quanto à precisão da manipulação, à oclusão, à separabilidade das manipulações, etc. As interfaces multitoque permitem múltiplas transformações espaciais, que podem ser realizadas em um objeto virtual mediante um gesto só. Por exemplo, um objeto pode ser rotacionado, escalado e transladado com dois dedos em um único gesto. Porém, alguns movimentos indesejados podem ocorrer acidentalmente. A técnica da separabilidade surge com a intenção de evitar operações indesejadas sobre superfícies multitoque. A oclusão é outro problema que ocorre em interfaces multitoque. Muitas vezes a mão do usuário esconde a visão do objeto com o qual se interage, ou então alguma ação da interface atrapalha a movimentação quando se clica sobre o local que dispara essa ação. Este trabalho estuda e propõe duas técnicas de separabilidade, para tentar diminuir os problemas que surgem devido ao excesso de liberdade das manipulações em interfaces multitoque, e avalia a eficácia dessas técnicas. As técnicas desenvolvidas não são só aplicáveis em objetos virtuais simples, também são para objetos virtuais do tipo WIMP (windows, icons, menus, pointer), com o objetivo de diminuir a oclusão. Uma série de testes foi feita para avaliar pontos como a precisão, oclusão, tempo para a realização das tarefas e facilidade de uso. / [en] The multitouch technology is emerging as a trend in recent years. The multitouch interfaces allow interacting with a virtual object directly, similar to a real object. However, this technology has not only advantages. There are several issues to be resolved, such as the accuracy of the manipulation, the occlusion, the separability of the manipulation, etc. The multitouch interfaces allow multiple spatial transformations that can be performed on a virtual object with only a gesture. For example, an object can be rotated, translated and scaled with two fingers with a single gesture. However, some unwanted movements may occur accidentally. The technique of separability appears with the intent to prevent unwanted movements on multitouch surfaces. Occlusion is another problem that occurs in multitouch interfaces. Often the user s hand hides the vision of the object with which he/she interacts; or the user s action on interface hinders the movement when it clicks on a bottom that triggers action. This dissertation studies, proposes and evaluates two techniques of separability, aiming to reduce the problems that arise due to excessive freedom of manipulation in multi-touch interfaces, and evaluates the efficiency of these techniques. The techniques developed are not only applicable in simple virtual objects; they are also for WIMP (windows, icons, menus, pointer) objects, aiming to reduce occlusion. A series of tests was performed to evaluate precision, occlusion time for completion of task, and ease of use.

[pt] Investigamos dois métodos de clusterização com restrições nas partições geradas: a clusterização explicável, em que a partição deve ser induzida por uma árvore de decisão binária (ou seja, por cortes paralelos aos eixos); e a clusterização de tamanho mínimo, na qual todos os clusters devem ter pelo menos um número predeterminado de elementos. Para a clusterização explicável, apresentamos algoritmos e garantias teóricas para as funções de custo k-centers, k-medians, k-means e espaçamento mínimo. Introduzimos também três algoritmos práticos para a popular função de custo k-means: ExGreedy, com resultados geralmente melhores do que os de algoritmos comparáveis na literatura; ExShallow, com um termo de penalidade relacionado à profundidade da árvore que induz a partição, permitindo um equilíbrio entre desempenho (redução da função de custo) e explicabilidade (geração de árvores mais rasas); e ExBisection, que, até onde sabemos, é o primeiro algoritmo de clusterização explicável baseado em árvores de decisão para a função de custo k-means que constrói uma partição explicável do zero (ou seja, sem usar uma partição irrestrita como ponto de partida). Para a clusterização de tamanho mínimo, focamos em medidas interclusterização. Mostramos que Single-Linkage, o algoritmo que maximiza o espaçamento mínimo, também maximiza o custo da árvore de geração mínima de um grafo induzido pela partição gerada por ele; no entanto, este algoritmo tende a gerar muitos clusters pequenos, o que motiva a busca por algoritmos com bons resultados para essas funções de custo que garantam um número mínimo de elementos por cluster. Introduzimos um algoritmo de aproximação para cada função de custo e apresentamos os resultados de experimentos que mostram que eles produzem partições com melhores resultados do que o popular algoritmo k-means para essas instâncias do problema de clusterização. / [en] We investigate two methods of clustering with constraints on the partitions being generated: explainable clustering, in which the partition must be induced by a binary decision tree (i.e., by cuts that are parallel to the axes); and minimum-size clustering, in which all clusters must have at least a predetermined number of elements. For explainable clustering, we present theoretical algorithms and bounds for the k-centers, k-medians, k-means, and minimum-spacing cost functions. We also introduce three practical algorithms for the popular k-means cost function: ExGreedy, which presents results generally better than comparable algorithms in the literature; ExShallow, with a penalty term related to the depth of the tree that induces the partition, allowing for a trade-off between performance (reducing the cost function) and explainability (generating shallower trees); and ExBisection, to our knowledge the first explainable clustering algorithm based on decision trees for the k-means cost function that builds an explainable partition from scratch (i.e., without starting from an unrestricted partition). For minimum-size clustering, our focus is on inter-clustering measures. We show that Single-Linkage, the algorithm that maximizes the minimum spacing, also maximizes the minimum-spanning-tree cost of a graph induced by the partition it generates; however, it is also prone to generating small clusters, which motivates the search for algorithms that perform well for these cost functions without suffering from this tendency. We introduce one approximation algorithm for each cost function, and present the results of experiments showing that they produce partitions that perform better than the popular k-means algorithm for these instances of the clustering task.