abstract: Quad-dominant (QD) meshes, i.e., three-dimensional, 2-manifold polygonal meshes comprising mostly four-sided faces (i.e., quads), are a popular choice for many applications such as polygonal shape modeling, computer animation, base meshes for spline and subdivision surface, simulation, and architectural design. This thesis investigates the topic of connectivity control, i.e., exploring different choices of mesh connectivity to represent the same 3D shape or surface. One key concept of QD mesh connectivity is the distinction between regular and irregular elements: a vertex with valence 4 is regular; otherwise, it is irregular. In a similar sense, a face with four sides is regular; otherwise, it is irregular. For QD meshes, the placement of irregular elements is especially important since it largely determines the achievable geometric quality of the final mesh. Traditionally, the research on QD meshes focuses on the automatic generation of pure quadrilateral or QD meshes from a given surface. Explicit control of the placement of irregular elements can only be achieved indirectly. To fill this gap, in this thesis, we make the following contributions. First, we formulate the theoretical background about the fundamental combinatorial properties of irregular elements in QD meshes. Second, we develop algorithms for the explicit control of irregular elements and the exhaustive enumeration of QD mesh connectivities. Finally, we demonstrate the importance of connectivity control for QD meshes in a wide range of applications. / Dissertation/Thesis / Doctoral Dissertation Computer Science 2014

On étudie dans cette thèse la correspondance de Satake géométrique. Un premier résultat est l’identification de la forme d’intersection au travers de la correspondance de Satake géométrique. En effet elle est égale à la forme contravariante "tordue"par l’involution de Schützenberger. On fait alors une conjecture combinatoire afin de démontrer que la base de Mirkovic ́ et Vilonen est compatible avec l’involution de Schützenberger. On démontre cette conjecture dans le cas où l’algèbre de Lie est sl2. Les outils combinatoires développés pour démontrer cette conjecture permettent, en outre, de prouver que la base semicanonique duale coïncide, pour sl2, avec la base de Mirovic et Vilonen généralisée. / In this thesis we study geometric Satake correspondance. First we identify the intersection form throught the correspondance. It equals a contravariant form twisted by Schützenberger's involution. Then we use a combinatoric conjecture to demonstrate the compatibility of the Mirkovic and Vilonen basis with the Schützenberger involution. We demonstrate this conjecture for the sl2 case. The combinatoric tools created to demonstrate this conjecture allow us to demonstrate that the dual semicanonical basis semicanonique duale equals the generalized Mirovic et Vilonen basis.

Spatial data (e.g., points) have extensive applications in practice, such as spatial databases, Location-Based Services, spatial computing, social analyses, computational geometry, graph design, medical imaging, etc. Geometric queries, such as geometric range queries (i.e., finding points inside a geometric range) and nearest neighbor queries (i.e., finding the closest point to a given point), are fundamental primitives to analyze and retrieve information over spatial data. For example, a medical researcher can query a spatial dataset to collect information about patients in a certain geometric area to predict whether there will be a dangerous outbreak of a particular disease (e.g., Ebola or Zika). With the dramatic increase on the scale and size of data, many companies and organizations are outsourcing significant amounts of data, including significant amounts of spatial data, to public cloud data services in order to minimize data storage and query processing costs. For instance, major companies and organizations, such as Yelp, Foursquare and NASA, are using Amazon Web Services as their public cloud data services, which can save billions of dollars per year for those companies and organizations. However, due to the existence of attackers (e.g., a curious administrator or a hacker) on remote servers, users are worried about the leakage of their private data while storing and querying those data on public clouds. Searchable Encryption (SE) is an innovative technique to protect the data privacy of users on public clouds without losing search functionalities on the server side. Specifically, a user can encrypt its data with SE before outsourcing data to a public server, and this public server is able to search encrypted data without decryption. Many SE schemes have been proposed to support simple queries, such as keyword search. Unfortunately, how to efficiently and securely support geometric queries over encrypted spatial data remains open. In this dissertation, to protect the privacy of spatial data in public clouds while still maintaining search functions without decryption, we propose a set of new SE solutions to support geometric queries, including geometric range queries and nearest neighbor queries, over encrypted spatial data. The major contributions of this dissertation focus on two aspects. First, we enrich search functionalities by designing new solutions to carry out secure fundamental geometric search queries, which were not supported in previous works. Second, we minimize the performance gap between theory and practice by building novel schemes to perform geometric queries with highly efficient search time and updates over large-scale encrypted spatial data. Specifically, we first design a scheme supporting circular range queries (i.e., retrieving points inside a circle) over encrypted spatial data. Instead of directly evaluating compute-then-compare operations, which are inefficient over encrypted data, we use a set of concentric circles to represent a circular range query, and then verify whether a data point is on any of those concentric circles by securely evaluating inner products over encrypted data. Next, to enrich search functionalities, we propose a new scheme, which can support arbitrary geometric range queries, such as circles, triangles and polygons in general, over encrypted spatial data. By leveraging the properties of Bloom filters, we convert a geometric range search problem to a membership testing problem, which can be securely evaluated with inner products. Moving a step forward, we also build another new scheme, which not only supports arbitrary geometric range queries and sub-linear search time but also enables highly efficient updates. Finally, we address the problem of secure nearest neighbor search on encrypted large-scale datasets. Specifically, we modify the algorithm of nearest neighbor search in advanced tree structures (e.g., R-trees) by simplifying operations, where evaluating comparisons alone on encrypted data is sufficient to efficiently and correctly find nearest neighbors over datasets with millions of tuples.

Abstract Axially moving material problems are concerned with the dynamic response, vibration and stability of slender members which are in a state of translation. In Finland these are particularly important in the functioning of paper machines, in which out of plane vibration in the paper web, known as flutter, which from the point of view of mechanics is a phenomenon typical of an axially moving material, limits operation speeds and therefore the productivity of the machines. This subject links together a number of physical phenomena associated with aerodynamics, web movement, material behaviour and the geometry of the system. The aim of this research is to present a theoretical and numerical formulation of the nonlinear dynamic analysis of an axially moving web. The theoretical model is based on a mixed description of the continuum problem in the context of the dynamics of initially stressed solids. Membrane elasticity is included via a finite strain model, and the membrane transport speed through a kinematical study. Hamilton's principle provides nonlinear equations which describe the three-dimensional motion of the membrane. The incremental equations of Hamilton's principle are discretized by the finite element method. The formulation includes geometrically nonlinear effects: large displacements, variations in membrane tension and variations in transport velocity due to deformation. This novel numerical model was implemented by adding an axially moving membrane element to a FEM program which contains acoustic fluid elements and contact algorithms. This allowed analysis of problems including interaction with the surrounding air field and contact between supporting structures. The model was tested by comparing previous experiments and present nonlinear description of the dynamic behaviour of an axially moving web. The effects of contact between finite rolls and the membrane and interaction between the surrounding air and the membrane were included in the model. The results show that nonlinearities and coupling phenomena have a considerable effect on the dynamic behaviour of the system. The nonlinearities cause a noticeable stiffening of the membrane, and the vibration frequency of nonlinear system increases as the amplitude grows. At high values of transport velocity the first mode frequency passes over the second linear harmonic, and even the third. The results also show that the cylindrical supports have a distinct influence on the behaviour of an axially moving sheet. The boundary of the contact region clearly moves and weakens the nonlinear hardening phenomena that otherwise increase the fundamental frequency. This influence strengthens as the radius of the cylinders increases.

In this thesis we investigate the geometric and algorithmic aspects of the random-cluster model, a correlated bond percolation model of great importance in the field of mathematics and statistical mechanics. We focus on the computational and statistical efficiency of the single-bond or heat-bath Markov chain for the random-cluster model and develop algorithmic techniques that allow for an improvement from a previously known polynomial to a poly-logarithmic runtime scaling of updates for general graphs. The interplay between the (critical) cluster structure of the random-cluster model and algorithmic, as well as statistical, efficiencies is considered, leading to new exact identities. A complementary analysis of certain fragility properties of the Fortuin-Kasteleyn clusters provides new insights into fragmentation phenomena, culminating in a revised scaling relation for a related fragmentation power law exponent, previously only shown for the marginal bond percolation case. By utilising the established structural results, a dynamic fragmentation process is studied that allows for an extraction of characteristics of the equilibrium cluster structure by a careful analysis of the limiting fragments, as well as the entire evolution of the fragmentation process. Besides focussing on structural and computational aspects, in this dissertation we also analyse the efficiency of the coupling from the past perfect sampling algorithm for the random-cluster model via large-scale numerical simulations. Two key results are the particular, close to optimal, efficiency in the off-critical setting and the intriguing observation of its superiority compared to the alternative Chayes-Machta-Swendsen-Wang approach in three dimensions. Governed by a random runtime, the efficiency of the coupling from the past algorithm depends crucially on the fluctuations of the runtime. In this connection a compelling appearance of universal Gumbel fluctuations in the distribution of the runtime of the coupling from the past algorithm is established, both at and off criticality. Fluctuations at a tricritical point and at a discontinuous phase transition are shown to deviate from this Gumbel law. The above findings in two and three dimensions are supported by a rigorous analysis of certain aspects of the algorithm in one dimension, including a proof of the limiting Gumbel law.

Geometric morphometrics, the science about the study of shape, has developed much in the last twenty years. In this thesis I first study the reliability of the phylogenies built using geometric morphometrics. The effect of different evolutionary models, branch-length combinations, dimensionality and degrees of integration is explored using computer simulations. Unfortunately in the most common situations (presence of stabilizing selection, short distance between internal nodes and presence of integration) the reliability of the phylogenies is very low. Different empirical studies are analysed to estimate the degree of evolutionary integration usually found in nature. This gives an idea about how powerful the effect of integration is over the reliability of the phylogenies in empirical studies. Evolutionary integration is studied looking at the decrease of variance in the principal components of the tangent shape space using the independent contrasts of shape. The results suggest that empirical data usually show strong degrees of integration in most of the organisms and structures analysed. These are bad news, since strong degree of integration has devastating effects over the phylogenetic reliability, as suggested by our simulations. However, we also propose the existence of other theoretical situations in which strong integration may not translate into convergence between species, like perpendicular orientation of the integration patterns or big total variance relative to the distance between species in the shape space. Finally, geometric morphometrics is applied to the study of the evolution of shape in proteins. There are reasons to think that, because of their modular nature and huge dimensionality, proteins may show different patterns of evolutionary integration. Unfortunately, proteins also show strong functional demands, which influence their evolution and that cause strong integration patterns. Integration is then confirmed as a widespread property in the evolution of shape, which causes poor phylogenetic estimates.

The present work is based on the Visual Routine theory of Shimon Ullman. This theory holds that efficient visual perception is managed by first applying spatially parallel methods to an initial input image in order to construct the basic representation-maps of features within the image. Then, this phase is followed by the application of serial methods - visual routines - which are applied to the most salient items in these and other subsequently created maps. Recent work in the visual routine tradition is reviewed, as well as relevant psychological work on preattentive and attentive vision. An analysis is made of the problem of devising a visual routine language for computing geometric properties and relations. The most useful basic representations to compute directly from a world of 2-D geometric shapes are determined. An argument is made for the case that an experimental program is required to establish which basic operations and which methods for controlling them will lead to the efficient computation of geometric properties and relations. A description is given of an implemented computer system which can correctly compute, in images of simple 2-D geometric shapes, the properties vertical, horizontal, closed, and convex, and the relations inside, outside, touching, centred-in, connected, parallel, and being-part-of. The visual routines which compute these, the basic operations out of which the visual routines are composed, and the important logic which controls the goal-directed application of the routines to the image are all described in detail. The entire system is embedded in a Question-and-Answer system which is capable of answering questions of an image, such as "Find all the squares inside triangles" or "Find all the vertical bars outside of closed convex shapes." By asking many such questions about various test images, the effectiveness of the visual routines and their controlling logic is demonstrated. / Science, Faculty of / Computer Science, Department of / Graduate

We introduce geometrically partial comodules over coalgebras in monoidal categories, as an alternative notion to the notion of partial action and coaction of Hopf algebras introduced by Caenepeel and Janssen. We show that our new notion suits better if one wants to describe phenomena of partial actions in algebraic geometry. We show that under mild conditions, the category of geometric partial comodules is complete and cocomplete and the category of partial comodules over a Hopf algebra is lax monoidal. We develop a Hopf-Galois theory for geometric partial coactions to illustrate that our new notion might be a useful additional tool in Hopf algebra theory. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

No description available.

For assembly of product machine is necessary to evaluate a geometric accuracy of individual functional parts of the machine. This process is very demanding and time consuming. One of the reasons of mentioned problems is the lack of software (adaptation) for measuring of the accuracy of geometrical precision. This theses (diploma work) focuses at facilitating the development and creation of own application based on customer requirements and for measuring geometric accuracy with the Laser Tracker AT901 from Leica company. The aim is to create a basic application suitable for measurement of geometric accuracy, which would speed up this process, would be user-friendly, simple and open for further expansion.