<p> Given a point p and d + 1 sets (i.e., colours) of points in dimension d, the Colourful Feasibility Problem is to decide whether there are d + 1 points of different colours containing p in their convex hull; and if yes, find such a point set. The monochrome version of this problem, expressing p as a linear combination of d + 1 points in a set S, can be solved using traditional linear optimization algorithms. The Colourful Feasibility Problem was presented by Bárány and Onn in 1997, and it is still not known if a polynomial-time algorithm exists. The case where we have d colours in dimension d and no restriction on the size of the sets has been shown to be strongly NP-complete through a reduction of 3-SAT. We define the core of a configuration to be the intersection of the convex hulls of each colour. We start from the important subcase that we call Colourful Core Feasibility Problem where we have d + 1 points of each colour, and p in the core. By Bárány's 1982 Colourful Caratheodory Theorem, a solution is guaranteed to exist, and the problem is to exhibit one. This problem is described by Bárány and Onn as "an outstanding problem on the border line between tractable and intractable problems". Besides applications to combinatorics, The Colourful Feasibility Problem models a situation where we want to select a set of points that is both diverse and representative.</p> <p> While we have not found out whether the Colourful Core Feasibility Problem can be solved in polynomial time, our contributions are on both the theoretical and practical performance of algorithms to solve the Colourful Feasibility Problem. The algorithms proposed by Bárány and Onn are essentially geometric, and the complexity guarantees depend crucially on having p inside the core. We consider modifications of these algorithms which update multiple colours at each stage, as well a greedy heuristic where we choose the adjacent simplex of maximum volume in each iteration and a random sampling approach. Our test suite includes unstructured random problems, ill-conditioned problems, problems with a restricted number of solutions and infeasible problems. We conclude that the most robust and nearly fastest algorithm for the Colourful Core Feasibility Problem is the multi-update variant which yields substantial gains over the original ones. Alternative approaches based on nondefinite quadratic optimization problem and positive semidefinite relaxation, and a combinatorial algorithm not depending on having p in the core are also introduced. Finally, we give the first upper bound for the minimal number of colourful simplices containing a core point and the first improvement of the lower bound since Bárány's result in 1982.</p> / Thesis / Master of Science (MSc)

The study seeks to analyze the &ldquo / Tulip Revolution&rdquo / , its reasons and outcomes. With the collapse of the Soviet Union, newly independent Central Asian countries / Kyrgyzstan, Kazakhstan, Turkmenistan, Uzbekistan and Tajikistan emerged in the world politics as independent sates. However, used to be parts of big complex system of former Soviet Union and being lack of government experience in politic and economic area made them to dependent on external actors. One of the main external actors has become United States with its promotion of democracy and liberalization, while the Russia was challenging not to lose its political and economical influence in these states. As a result of these external powers&rsquo / policy, within the time the leaders of these states found themselves in the complex choices, pro-Western or pro-Russian. Therefore political and economic developments of these states have become vulnerable. For these reasons the &lsquo / coloured revolutions&rsquo / in post-Soviet states, which was the struggle between the pro-Western and pro-Russian elites, were not a coincidence. The study argues that although &ldquo / Tulip Revolution&rdquo / had similarities in its occurrence with previous &lsquo / colourful revolutions&rsquo / the main reasons of the &ldquo / Tulip Revolution&rdquo / were the internal reasons, external reasons were only the accelerator factors. Analyzing of these reasons is the main goal of thesis.

<p>Given colourful sets S_1,..., S_{d+1} of points in R^d and a point p in R^d, the colourful linear programming problem is to express p as a convex combination of points x_1,...,x_{d+1} with x_i in S_i for each i. This problem was presented by Bárány and Onn in 1997, it is still not known if a polynomial-time algorithm for the problem exists. The monochrome version of this problem, expressing p as a convex combination of points in a set S, is a traditional linear programming feasibility problem. The colourful Carathéodory Theorem, due to Bárány in 1982, provides a sufficient condition for the existence of a colourful set of points containing p in its convex hull. Bárány's result was generalized by Holmsen et al. in 2008 and by Arocha et al. in 2009 before being recently further generalized by Meunier and Deza. We study algorithms for colourful linear programming under the conditions of Bárány and their generalizations. In particular, we implement the Meunier-Deza algorithm and enhance previously used random case generators. Computational benchmarking and a performance analysis including a comparison between the two algorithms of Bárány and Onn and the one of Meunier and Deza, and random picking are presented.</p> / Master of Science (MSc)

The objective of this project is to challenge the traditional interior design of gynaecologist clinics and develop a fresh and innovative concept that enhances the overall experience for patients. By utilising colour, material, and form, this interior concept aims to transform the perception of healthcare facilities, ultimately improving the well-being and comfort of patients during gynaecological visits. To exemplify a different, more welcoming and safe environment, my experiments have involved using colour, material and form, as well as purpose designed chairs for the waiting room as well as the examination rooms, respectively. Besides this I have explored distractive elements during the patients’ examination. The design process for this project involved conducting qualitative research and studying existing gynaecologist clinic designs, patient experiences, and current trends in healthcare environments. Valuable insights has been gathered through interviews with healthcare professionals and patients, which helped identify areas for potential improvement. Additionally, the project explored the use of innovative design techniques, materials, and spatial configurations that foster a sense of privacy, and well- being. The design process also involves the development of design sketches and digital visualisations to aid in the visualisation and refinement of the interior concept. By utilising all design elements, the concept aims to create a health-promoting experience that ensures a safe, pleasant, and welcoming environment for both patients and staff.

Le théorème de Carathéodory coloré, prouvé en 1982 par Bárány, énonce le résultat suivant. Etant donnés d Å1 ensembles de points S1,SdÅ1 dans Rd , si chaque Si contient 0 dans son enveloppe convexe, alors il existe un sous-ensemble arc-en-ciel T µ SdÅ1 iÆ1 Si contenant 0 dans son enveloppe convexe, i.e. un sous-ensemble T tel que jT \Si j • 1 pour tout i et tel que 0 2 conv(T ). Ce théorème a donné naissance à de nombreuses questions, certaines algorithmiques et d’autres plus combinatoires. Dans ce manuscrit, nous nous intéressons à ces deux aspects. En 1997, Bárány et Onn ont défini la programmation linéaire colorée comme l’ensemble des questions algorithmiques liées au théorème de Carathéodory coloré. Parmi ces questions, deux ont particulièrement retenu notre attention. La première concerne la complexité du calcul d’un sous-ensemble arc-en-ciel comme dans l’énoncé du théorème. La seconde, en un sens plus générale, concerne la complexité du problème de décision suivant. Etant donnés des ensembles de points dans Rd , correspondant aux couleurs, il s’agit de décider s’il existe un sous-ensemble arc-en-ciel contenant 0 dans son enveloppe convexe, et ce en dehors des conditions du théorème de Carathéodory coloré. L’objectif de cette thèse est de mieux délimiter les cas polynomiaux et les cas “difficiles” de la programmation linéaire colorée. Nous présentons de nouveaux résultats de complexités permettant effectivement de réduire l’ensemble des cas encore incertains. En particulier, des versions combinatoires du théorème de Carathéodory coloré sont présentées d’un point de vue algorithmique. D’autre part, nous montrons que le problème de calcul d’un équilibre de Nash dans un jeu bimatriciel peut être réduit polynomialement à la programmation linéaire coloré. En prouvant ce dernier résultat, nous montrons aussi comment l’appartenance des problèmes de complémentarité à la classe PPAD peut être obtenue à l’aide du lemme de Sperner. Enfin, nous proposons une variante de l’algorithme de Bárány et Onn, calculant un sous ensemble arc-en-ciel contenant 0 dans son enveloppe convexe sous les conditions du théorème de Carathéodory coloré. Notre algorithme est clairement relié à l’algorithme du simplexe. Après une légère modification, il coïncide également avec l’algorithme de Lemke, calculant un équilibre de Nash dans un jeu bimatriciel. La question combinatoire posée par le théorème de Carathéodory coloré concerne le nombre de sous-ensemble arc-en-ciel contenant 0 dans leurs enveloppes convexes. Deza, Huang, Stephen et Terlaky (Colourful simplicial depth, Discrete Comput. Geom., 35, 597–604 (2006)) ont formulé la conjecture suivante. Si jSi j Æ d Å1 pour tout i 2 {1, . . . ,d Å1}, alors il y a au moins d2Å1 sous-ensemble arc-en-ciel contenant 0 dans leurs enveloppes convexes. Nous prouvons cette conjecture à l’aide d’objets combinatoires, connus sous le nom de systèmes octaédriques, dont nous présentons une étude plus approfondie / The colorful Carathéodory theorem, proved by Bárány in 1982, states the following. Given d Å1 sets of points S1, . . . ,SdÅ1 µ Rd , each of them containing 0 in its convex hull, there exists a colorful set T containing 0 in its convex hull, i.e. a set T µ SdÅ1 iÆ1 Si such that jT \Si j • 1 for all i and such that 0 2 conv(T ). This result gave birth to several questions, some algorithmic and some more combinatorial. This thesis provides answers on both aspects. The algorithmic questions raised by the colorful Carathéodory theorem concern, among other things, the complexity of finding a colorful set under the condition of the theorem, and more generally of deciding whether there exists such a colorful set when the condition is not satisfied. In 1997, Bárány and Onn defined colorful linear programming as algorithmic questions related to the colorful Carathéodory theorem. The two questions we just mentioned come under colorful linear programming. This thesis aims at determining which are the polynomial cases of colorful linear programming and which are the harder ones. New complexity results are obtained, refining the sets of undetermined cases. In particular, we discuss some combinatorial versions of the colorful Carathéodory theorem from an algorithmic point of view. Furthermore, we show that computing a Nash equilibrium in a bimatrix game is polynomially reducible to a colorful linear programming problem. On our track, we found a new way to prove that a complementarity problem belongs to the PPAD class with the help of Sperner’s lemma. Finally, we present a variant of the “Bárány-Onn” algorithm, which is an algorithmcomputing a colorful set T containing 0 in its convex hull whose existence is ensured by the colorful Carathéodory theorem. Our algorithm makes a clear connection with the simplex algorithm. After a slight modification, it also coincides with the Lemke method, which computes a Nash equilibriumin a bimatrix game. The combinatorial question raised by the colorful Carathéodory theorem concerns the number of positively dependent colorful sets. Deza, Huang, Stephen, and Terlaky (Colourful simplicial depth, Discrete Comput. Geom., 35, 597–604 (2006)) conjectured that, when jSi j Æ d Å1 for all i 2 {1, . . . ,d Å1}, there are always at least d2Å1 colourful sets containing 0 in their convex hulls. We prove this conjecture with the help of combinatorial objects, known as the octahedral systems. Moreover, we provide a thorough study of these objects

<p>This thesis deals with combinatorial and geometric aspects of linear optimization, and consists of two parts.</p> <p>In the first part, we address a conjecture formulated in 2008 and stating that the largest possible average diameter of a bounded cell of a simple hyperplane arrangement of n hyperplanes in dimension d is not greater than the dimension d. The average diameter is the sum of the diameters of each bounded cell divided by the total number of bounded cells, and then we consider the largest possible average diameter over all simple hyperplane arrangements. This quantity can be considered as an indication of the average complexity of simplex methods for linear optimization. Previous results in dimensions 2 and 3 suggested that a specific type of extensions, namely the covering extensions, of the cyclic arrangement might achieve the largest average diameter. We introduce a method for enumerating the covering extensions of an arrangement, and show that covering extensions of the cyclic arrangement are not always among the ones achieving the largest diameter.</p> <p>The software tool we have developed for oriented matroids computation is used to exhibit a counterexample to the hypothesized minimum number of external facets of a simple arrangement of n hyperplanes in dimension d; i.e. facets belonging to exactly one bounded cell of a simple arrangement. We determine the largest possible average diameter, and verify the conjectured upper bound, in dimensions 3 and 4 for arrangements defined by no more than 8 hyperplanes via the associated uniform oriented matroids formulation. In addition, these new results substantiate the hypothesis that the largest average diameter is achieved by an arrangement minimizing the number of external facets.</p> <p>The second part focuses on the colourful simplicial depth, i.e. the number of colourful simplices in a colourful point configuration. This question is closely related to the colourful linear programming problem. We show that any point in the convex hull of each of (d+1) sets of (d+1) points in general position in R^d is contained in at least (d+1)²/2 simplices with one vertex from each set. This improves the previously established lower bounds for d>=4 due to Barany in 1982, Deza et al in 2006, Barany and Matousek in 2007, and Stephen and Thomas in 2008.</p> <p>We also introduce the notion of octahedral system as a combinatorial generalization of the set of colourful simplices. Configurations of low colourful simplicial depth correspond to systems with small cardinalities. This construction is used to find lower bounds computationally for the minimum colourful simplicial depth of a configuration, and, for a relaxed version of the colourful depth, to provide a simple proof of minimality.</p> / Doctor of Philosophy (PhD)

The thesis is based on questionnaire survey conducted among 136 so called "green and colourful" respondents. The term "the colourful and the green" comes from the professor of environmental sociology, Hana Librová, and refers to people living the ecologically beneficial lifestyle that can be characterized by voluntary or intentional modesty. The target of the survey was to find out whether these people are influenced in their lifestyle by books or which books would articulate their worldview the best; what books they resonate with. Often repeated titles formed a "green influential literary canon" that is further analyzed in the thesis. First, the canon as a whole is examined, second the three most frequent books are studied with an ecocritical approach. In the canon, a minimum titles from the field of deep ecology, nature writing as well as science fiction or utopia were registered. Despite the expectation, there were many books related to New Age movement in the canon as well as pop-cultural spiritual writings. Nevertheless, books concerning native americans, together with eco- philosophical works largely dominated. Functions that the publications fulfill for the readers are seen as a clamp of diverse books in the canon. There are three main functions defined and further explained:...

The colourful past of the late 18th century marquetry furniture has seldom been highlighted. Through ageing and environmental influences, colourful marquetry furniture has lost their original expression. The current knowledge of how Swedish cabinet-makers in the late 18th century used dyes to colour their furniture is limited. Trace of colour has been observed and the use of dyes has been mentioned, but deeper research in this filed is missing. A visual examination and studies of archive documents and previous research have been performed to investigate the colourful past of Gottlieb Iwerssons masterpiece, a secretaire in Gustavian style made for the king Gustav III. The result shows that the secretaire has a colourful past in accordance with its original drawing. A hypothetical picture has been created to illustrate the colourful original appearance.

SLOVENE NATIONAL THEATRE IN LJUBLJANA Author Report Of The Diploma Work Author: Bc. Petr Hýl Supervisor: doc. ing. arch. Zdeněk Makovský