- Úvod
- Ústav
- Lidé
- Výzkum
- Aplikace
- Semináře a akce
- Knihovna
- Doktorské studium
- Kariéra
In Siam Journal on Computing , ročník 46, svazek 5, strana 1574-1602, 2017. ISSN 0097-5397.
We consider the following geometric optimization problem: find a convex polygon of maximum area contained in a given simple polygon P with n vertices. We give a randomized near-linear-time (1-\varepsilon)-approximation algorithm for this problem: in O(n( \log^2 n + (1/\varepsilon^3) \log n + 1/\varepsilon^4)) time we find a convex polygon contained in P that, with probability at least 2/3, has area at least (1-\varepsilon) times the area of an optimal solution. We also obtain similar results for the variant of computing a convex polygon inside P with maximum perimeter. To achieve these results we provide new results in geometric probability. The first result is a bound relating the area of the largest convex body inside P to the probability that two points chosen uniformly at random inside P are mutually visible. The second result is a bound on the expected value of the difference between the perimeter of any planar convex body K and the perimeter of the convex hull of a uniform random sample inside K.
In SIAM Journal on Discrete Mathematics , ročník 31, svazek 2, strana 945-982, 2017. ISSN 0895-4801.
In a series of four papers we prove the following relaxation of the Loebl--Komlós--Sós conjecture: For every alpha>0 there exists a number k_0 such that for every k>k_0, every n-vertex graph G with at least (0.5+alpha)n vertices of degree at least (1+alpha)k contains each tree T of order k as a subgraph. The method to prove our result follows a strategy similar to approaches that employ the Szemerédi regularity lemma: We decompose the graph G, find a suitable combinatorial structure inside the decomposition, and then embed the tree T into G using this structure. Since for sparse graphs G, the decomposition given by the regularity lemma is not helpful, we use a more general decomposition technique. We show that each graph can be decomposed into vertices of huge degree, regular pairs (in the sense of the regularity lemma), and two other objects each exhibiting certain expansion properties. In this paper, we introduce this novel decomposition technique.
In Geoscientific Model Development , ročník 10, svazek 10, strana 3635-3659, 2017. ISSN 1991-959X.
Urban areas are an important part of the climate system and many aspects of urban climate have a direct effect on human health and living conditions. This implies the need for a reliable tool for climatology studies that supports urban planning and development strategies. However, a realistic implementation of urban canopy processes still poses a serious challenge for weather and climate modelling for the current generation of numerical models. To address this demand, a new model of energy processes for urban environments was 5 developed as an Urban Surface Model (USM) and integrated as a module into the large-eddy simulation (LES) model PALM. The USM contains a multi-reflection radiation model for short and long wave radiation, calculation of the energy balance on horizontal and vertical impervious surfaces, thermal diffusion in ground, wall and roof materials and anthropogenic heat from transportation. The module also models absorption of radiation by resolved plant canopy (i.e. trees, shrubs). The USM was parallelized using MPI and performance testing demonstrates that the computational costs 10 of the USM are reasonable and the model scales well on typical cluster configurations. The module was fully integrated into PALM and is available via its online repository under GNU General Public License (GPL). The implementation was tested on a summer heat wave episode in the real conditions of a selected Prague crossroad. General patterns of temperature of various surface types (walls, pavement) are in good agreement with observations. The coupled LES-USM system appears to correct the bias found between observations and mesoscale model predictions for the near-surface air temperature. The results, however, 15 show a strong dependence on the prescribed surface and wall material properties. Their exact knowledge is thus essential for the correct prediction of the flow in the urban canopy layer.