|
|
Algorithms for Minkowski sums of polygons
Šimek, Daniel ; Patáková, Zuzana (advisor) ; Příhoda, Pavel (referee)
This bachelor's thesis deals with the Minkowski sum of two non-convex polygons in the plane. Specifically, it focuses on describing and comparing two methods for computing the Minkowski sum: the decomposition method and the convolution method. This thesis provides a detailed presentation of both methods, including necessary definitions and illustrative images. In the final chapter, both methods are compared using the CGAL C++ library on various inputs. 1
|
|
|
MDS matrices
Vlášková, Šárka ; Žemlička, Jan (advisor) ; Patáková, Zuzana (referee)
MDS matrices are widely used in coding theory and cryptography (e.g. in diffusion layers of block ciphers or hash functions), but the construction of MDS matrices is not at all trivial, especially when we require some other suitable properties (involution, efficiency of implementation). That is why we will deal with the construction of MDS matrices (with other properties) in this thesis. We will show a construction of MDS matrices based on Cauchy matrices and on Vandermonde matrices. Then we will present an algorithm for testing whether a given matrix is MDS. And finally, we will show a construction of MDS matrices based on Companion matrices, which is very convenient for lightweight cryptography. 1
|
|
|
Hyperfields and their applications in tropical geometry or matroid theory
Andr, Břetislav ; Patáková, Zuzana (advisor) ; Šťovíček, Jan (referee)
Hyperfields are algebraic structures generalizing the concept of an algebraic field. In contrast to classical fields, summation in a hyperfield is multivalued, that is, the sum of two elements is not a single element, but a whole set of elements. Hyperfields find practical use in the theory of matroids and in tropical geometry, a variant of algebraic geometry. Matroid is an algebraic structure generalizing the concept of linear independence. There exist more types of matroids expanding the basic definition, e.g. oriented or valuated matroids. All of these definitions can be generalized to a single concept of an F-matroid, where F is a hyperfield. Tropical geometry is concerned with similar problems as algebraic geometry, only over the so-called tropical semifield. It finds many applications due to its combinatorial nature. Tropical geometry and algebraic geometry are closely tied by the so-called Litvinov-Maslov dequantization and hyperfields may be used to describe its generalized version. 1
|
|
|
Art gallery problem
Smolíková, Natálie ; Patáková, Zuzana (advisor) ; Žemlička, Jan (referee)
In this thesis, we study a classical problem in computational geometry, the Art Gallery Problem. The Art Gallery Problem originates from the question of what is the minimum number of guards required to see the entire gallery. The main goal of this paper is to provide proofs that ⌊n 3 ⌋ guards are sufficient for a simple polygon, and that ⌊n 4 ⌋ guards are sufficient for an orthogonal polygon. Our proof of the orthogonal version is a correction of Jorge Urrutia's proof. We also study the optimality of the results and the placement of guards. 1
|
|
|
Nonassociativity in two operations
Lehká, Martina ; Drápal, Aleš (advisor) ; Patáková, Zuzana (referee)
This thesis follows up mainly on the research of Drápal and Valent, who studied the nonassociativity of one quasigroup operation. Its central objective is to examine the number of triples (x, y, z) ∈ Q3 such that (x ∗ y) ◦ z = x ∗ (y ◦ z), where (Q, ∗) and (Q, ◦) are two quasigroups, |Q| = n. Let a2(C) be the number of such triples in a quasigroup couple C. Call it the associativity index. Denote by a2(n) the minimal a2(C), where C is a couple of order n. By averaging the associativity index over all the principal isotopes of a quasigroup couple, we prove that a2(n) ≤ n2 (1+1/(n−1)), n > 2. We then characterize the couples C that, on average, attain a2(C) = n2 and we prove that this value is an improved upper bound on a2(n), n > 2. Furthermore, we begin research on couples of quasigroups isotopic to groups. Lastly, we present computational results with examples, including a2(4) = 8 and a2(5) = 9. 1
|
|
|
Problems in discrete geometry
Patáková, Zuzana ; Matoušek, Jiří (advisor) ; Bárány, Imre (referee) ; Valtr, Pavel (referee)
of doctoral thesis Problems in discrete geometry Zuzana Patáková This thesis studies three different questions from discrete geometry. A common theme for these problems is that their solution is based on algebraic methods. First part is devoted to the polynomial partitioning method, which par- titions a given finite point set using the zero set of a suitable polynomial. However, there is a natural limitation of this method, namely, what should be done with the points lying in the zero set? Here we present a general version dealing with the situation and as an application, we provide a new algorithm for the semialgebraic range searching problem. In the second part we study Ramsey functions of semialgebraic predi- cates. Conlon, Fox, Pach, Sudakov, and Suk constructed the first examples of semialgebraic predicates with the Ramsey function bounded from below by a tower function. We reduce the dimension of the ambient space in their construction and as a consequence, we provide a new geometric Ramsey-type theorem with a large Ramsey function. Last part is devoted to reptile simplices. A simplex S is k-reptile if it can be tiled by k simplices with disjoint interiors that are all mutually congruent and similar to S. We show that four-dimensional k-reptile simplices can exist only for k = m2 , where m ≥ 1...
|
|
|
The Helly numbers of systems of sets with bounded algebraic and topological complexity
Sosnovec, Jakub ; Tancer, Martin (advisor) ; Patáková, Zuzana (referee)
Maehara has shown that a family F of at least d+3 spheres in Rd has a nonempty intersection if every d+1 spheres from F have a nonempty intersection. We extend this Helly-type result in two directions. On the one hand, we show an analogous theorem holds for families of pseudospheres, i.e., systems of sets such that the intersection of any nonempty subsystem is homeomorphic to a sphere of some dimension or is empty. On the other hand, a sphere in Rd can be expressed as the zero set of a real polynomial. For a set of polynomials P, the Helly number of the family of zero sets of polynomials from P is bounded by the dimension of the vector space generated by P. For spheres, however, Maehara's result gives a stronger bound. We show some general sufficient assumptions that allow better bounds on the Helly numbers in this context. Powered by TCPDF (www.tcpdf.org)
|
|
|
Deriving a pseudomanifold of dimension 3 from nonassociative triples
Spišák, Martin ; Drápal, Aleš (advisor) ; Patáková, Zuzana (referee)
The non-associative properties of quasigroups are useful in cryptography. A. Drápal and I. M. Wanless have recently analyzed the existence of a max- imally non-associative quasigroup of order n in their work, but there remain orders n for which the existence is not known. This thesis is an introduction to a new method of tackling the problem. After presenting the most recent results and hinting at a possible crypto- graphic application, the thesis proposes the construction of a 3-dimensional abstract simplicial complex from non-associative triples of a finite quasigroup. It shows that the complex forms of a union of closed orientable pseudomani- folds of dimension 3. For orders up to 6, we independently verify the findings of Ježek and Kepka regarding the associativity spectrum of n and classify possible decompositions of the non-associativity complexes into strongly con- nected components by analyzing their dual graphs. The main result of the thesis performs the first step towards resolving the singularities in the complex. We show that links of vertices in the complex have solvable singularities, enabling us to normalize the links of vertices algorithmically. Lastly, we illustrate the types of vertex neighborhoods on examples of small quasigroups by calculating the genera of their components. 1
|
|
|
Problems in discrete geometry
Patáková, Zuzana ; Matoušek, Jiří (advisor) ; Bárány, Imre (referee) ; Valtr, Pavel (referee)
of doctoral thesis Problems in discrete geometry Zuzana Patáková This thesis studies three different questions from discrete geometry. A common theme for these problems is that their solution is based on algebraic methods. First part is devoted to the polynomial partitioning method, which par- titions a given finite point set using the zero set of a suitable polynomial. However, there is a natural limitation of this method, namely, what should be done with the points lying in the zero set? Here we present a general version dealing with the situation and as an application, we provide a new algorithm for the semialgebraic range searching problem. In the second part we study Ramsey functions of semialgebraic predi- cates. Conlon, Fox, Pach, Sudakov, and Suk constructed the first examples of semialgebraic predicates with the Ramsey function bounded from below by a tower function. We reduce the dimension of the ambient space in their construction and as a consequence, we provide a new geometric Ramsey-type theorem with a large Ramsey function. Last part is devoted to reptile simplices. A simplex S is k-reptile if it can be tiled by k simplices with disjoint interiors that are all mutually congruent and similar to S. We show that four-dimensional k-reptile simplices can exist only for k = m2 , where m ≥ 1...
|
|
|
The Helly numbers of systems of sets with bounded algebraic and topological complexity
Sosnovec, Jakub ; Tancer, Martin (advisor) ; Patáková, Zuzana (referee)
Maehara has shown that a family F of at least d+3 spheres in Rd has a nonempty intersection if every d+1 spheres from F have a nonempty intersection. We extend this Helly-type result in two directions. On the one hand, we show an analogous theorem holds for families of pseudospheres, i.e., systems of sets such that the intersection of any nonempty subsystem is homeomorphic to a sphere of some dimension or is empty. On the other hand, a sphere in Rd can be expressed as the zero set of a real polynomial. For a set of polynomials P, the Helly number of the family of zero sets of polynomials from P is bounded by the dimension of the vector space generated by P. For spheres, however, Maehara's result gives a stronger bound. We show some general sufficient assumptions that allow better bounds on the Helly numbers in this context. Powered by TCPDF (www.tcpdf.org)
|
guest ::
RSS feed.