• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Of all publications in the section: 14
Sort:
by name
by year
Article
Blagojević P., Karasev R., Magazinov A. Discrete and Computational Geometry. 2018. Vol. 60. No. 2. P. 406-419.

A celebrated result of Dol'nikov, and of \v{Z}ivaljevi\'c and Vre\'cica, asserts that for every collection of $m$ measures $\mu_1,\dots,\mu_m$  on the Euclidean space $\mathbb R^{n + m - 1}$ there exists a projection onto an $n$-dimensional vector subspace $\Gamma$ with a point in it at depth at least $\tfrac{1}{n + 1}$ with respect to each associated $n$-dimensional marginal measure $\Gamma_*\mu_1,\dots,\Gamma_*\mu_m$.

In this paper we consider a natural extension of this result and ask for a minimal dimension of a Euclidean space in which one can require that for any collection of $m$ measures there exists a vector subspace $\Gamma$ with a point in it at depth slightly greater than $\tfrac{1}{n + 1}$ with respect to each $n$-dimensional marginal measure. In particular, we prove that if the required depth is $\tfrac{1}{n + 1} + \tfrac{1}{3(n + 1)^3}$ then the increase in the dimension of the ambient space is a linear function in both $m$ and $n$.

Added: Oct 4, 2018
Article
Magazinov A., Pór A. Discrete and Computational Geometry. 2018. Vol. 59. No. 2. P. 477-505.

Let $\mu$ be a Borel probability measure in $\mathbb R^d$. For a $k$-flat $\alpha$ consider the value $\inf \mu(H)$, where $H$ runs through all half-spaces containing $\alpha$. This infimum is called the {\it half-space depth} of $\alpha$.

Bukh, Matou\v{s}ek and Nivasch conjectured that for every $\mu$ and every $0 \leq k < d$ there exists a $k$-flat with the depth at least $\tfrac{k + 1}{k + d + 1}$. The Rado Centerpoint Theorem implies a lower bound of $\tfrac{1}{d + 1 - k}$ {\it (the Rado bound)}, which is, in general, much weaker. Whenever the Rado bound coincides with the bound conjectured by Bukh, Matou\v{s}ek and Nivasch, i.e., for $k = 0$ and $k = d - 1$, it is known to be optimal.

In this paper we show that for all other pairs $(d, k)$ one can improve on the Rado bound. If $k = 1$ and $d \geq 3$ we show that there is a 1-dimensional line with the depth at least $\tfrac{1}{d} + \tfrac{1}{3d^3}$. As a corollary, for all $(d, k)$ satisfying $0 < k < d - 1$ there exists a $k$-flat with depth at least $\tfrac{1}{d + 1 - k} + \tfrac{1}{3(d + 1 - k)^3}$.

Added: Oct 4, 2018
Article
Magazinov A. Discrete and Computational Geometry. 2013. Vol. 49. No. 2. P. 200-220.

Let P_λ be a homogeneous Poisson point process of rate λ in the Clifford torus T^2⊂E^4. Let (f0,f1,f2,f3) be the f-vector of conv P_λ and let \bar{v} be the mean valence of a vertex of the convex hull. Asymptotic expressions for 𝖤 f_1, 𝖤 f_2, 𝖤 f_3 and 𝖤 \bar{v} as λ→∞ are proved in this paper.

Added: Oct 4, 2018
Article
Gaifullin A., Gaifullin S.A. Discrete and Computational Geometry. 2014. Vol. 51. No. 3. P. 650-665.

At the end of the 19th century Bricard discovered the phenomenon of flexible polyhedra, that is, polyhedra with rigid faces and hinges at edges that admit non-trivial flexes. One of the most important results in this field is a theorem of Sabitov, asserting that the volume of a flexible polyhedron is constant during the flexion. In this paper we study flexible polyhedral surfaces in ℝ3, doubly periodic with respect to translations by two non-collinear vectors, that can vary continuously during the flexion. The main result is that the period lattice of a flexible doubly periodic surface that is homeomorphic to the plane cannot have two degrees of freedom

Added: Dec 17, 2014
Article
Shitov Y. Discrete and Computational Geometry. 2019. Vol. 61. No. 3. P. 653-660.

A Euclidean distance matrix D(α) is defined by D_ij=(α_i−α_j)^2, where α=(α_1,…,α_n) is a real vector. We prove that D(α) cannot be written as a sum of [2sqrt(n)−2] nonnegative rank-one matrices, provided that the coordinates of α are algebraically independent. As a corollary, we provide an asymptotically optimal separation between the complexities of quantum and classical communication protocols computing a given matrix in expectation.

Added: Mar 15, 2018
Article
Esterov A. I. Discrete and Computational Geometry. 2010. Vol. 44. No. 1. P. 96-148.

For a system of polynomial equations, whose coefficients depend on parameters, the Newton polyhedron of its discriminant is computed in terms of the Newton polyhedra of the coefficients. This leads to an explicit formula (involving mixed fiber polyhedra and Euler obstructions of toric varieties) in the unmixed case, suggests certain open questions in general, and generalizes a number of similar known results.

Added: Dec 10, 2012
Article
Durand B., Shen A., Vereshchagin N. Discrete and Computational Geometry. 2019. P. 1-30.

We establish a structure theorem for the family of Ammann A2 tilings of the plane. Using that theorem we show that every Ammann A2 tiling is self-similar in the sense of Solomyak (Discret Comput Geom 20:265–279, 1998). By the same techniques we show that Ammann A2 tilings are not robust in the sense of Durand et al. (J Comput Syst Sci 78(3):731–764, 2012).

Added: Jun 6, 2019
Article
Хованский А. Г., Timorin V. Discrete and Computational Geometry. 2014. Vol. 52. No. 4. P. 806-823.

If the complement of a closed convex set in a closed convex cone is bounded, then this complement minus the apex of the cone is called a coconvex set. Coconvex sets appear in singularity theory (they are closely related to Newton diagrams) and in commutative algebra. Such invariants of coconvex sets as volumes, mixed volumes, number of integer points, etc., play an important role. This paper aims at extending various results from the theory of convex bodies to the coconvex setting. These include the Aleksandrov–Fenchel inequality and the Ehrhart duality.

Added: Sep 29, 2014
Article
Magazinov A., Gavrilyuk A., Garber A. Discrete and Computational Geometry. 2015. Vol. 53. No. 2. P. 245-260.

We show that the Voronoi conjecture is true for parallelohedra with simply connected δδ-surfaces. That is, we show that if the boundary of parallelohedron PP remains simply connected after removing closed nonprimitive faces of codimension 2, then PP is affinely equivalent to a Dirichlet–Voronoi domain of some lattice. Also, we construct the ππ-surface associated with a parallelohedron and give another condition in terms of a homology group of the constructed surface. Every parallelohedron with a simply connected δδ-surface also satisfies the condition on the homology group of the ππ-surface.

Added: Oct 4, 2018
Article
Garber A., Gavrilyuk A., Magazinov A. Discrete and Computational Geometry. 2015. Vol. 53. No. 2. P. 245-260.

We show that the Voronoi conjecture is true for parallelohedra with simply connected δ-surfaces. That is, we show that if the boundary of parallelohedron P remains simply connected after removing closed nonprimitive faces of codimension 2, then P is affinely equivalent to a Dirichlet–Voronoi domain of some lattice. Also, we construct the π-surface associated with a parallelohedron and give another condition in terms of a homology group of the constructed surface. Every parallelohedron with a simply connected δ-surface also satisfies the condition on the homology group of the π-surface.

Added: Mar 16, 2016
Article
Kalinin N. Discrete and Computational Geometry. 2017. Vol. 58. No. 1. P. 158-179.

Suppose that there exists a hypersurface with the Newton polytope Δ, which passes through a given set of subvarieties. Using tropical geometry, we associate a subset of Δ to each of these subvarieties. We prove that a weighted sum of the volumes of these subsets estimates the volume of Δ from below. As a particular application of our method we consider a planar algebraic curve C which passes through generic points p1,…,pn with prescribed multiplicities m1,…,mn. Suppose that the minimal lattice width ω(Δ) of the Newton polygon Δ of the curve C is at least max(mi). Using tropical floor diagrams (a certain degeneration of p1,…,pn on a horizontal line) we prove that

area(Δ)≥12n∑i=1m2i−S,  where S=12max(n∑i=1s2i|si≤mi,n∑i=1si≤ω(Δ)).

In the case m1=m2=⋯=m≤ω(Δ) this estimate becomes area(Δ)≥12(n−ω(Δ)m)m2. That rewrites as d≥(√n−12−12√n)m for the curves of degree d. We consider an arbitrary toric surface (i.e. arbitrary Δ) and our ground field is an infinite field of any characteristic, or a finite field large enough. The latter constraint arises because it is not a priori clear what is a collection of generic points in the case of a small finite field. We construct such collections for fields big enough, and that may be also interesting for the coding theory.

Added: May 16, 2017
Article
Podolskii V. V., Grigoriev D. Discrete and Computational Geometry. 2018. Vol. 59. No. 3. P. 507-552.

Tropical algebra is an emerging field with a number of applications in various areas of mathematics. In many of these applications appeal to tropical polynomials allows studying properties of mathematical objects such as algebraic varieties from the computational point of view. This makes it important to study both mathematical and computational aspects of tropical polynomials. In this paper we prove a tropical Nullstellensatz, and moreover, we show an effective formulation of this theorem. Nullstellensatz is a natural step in building algebraic theory of tropical polynomials and its effective version is relevant for computational aspects of this field. On our way we establish a simple formulation of min-plus and tropical linear dualities. We also observe a close connection between tropical and min-plus polynomial systems.

Added: Oct 16, 2018
Article
Shabanov L., Raigorodskii A. Discrete and Computational Geometry. 2016. Vol. 56. No. 3. P. 814-832.

The classical Turán theorem determines the minimum number of edges in a graph on n vertices with independence number α. We consider unit-distance graphs on the Euclidean plane, i.e., graphs G= (V, E) with V⊂ R2 and E= {{x, y} : | x- y| = 1} , and show that the minimum number of edges in a unit-distance graph on n vertices with independence number α⩽ λn, λ∈[14,27], is bounded from below by the quantity 19-50λ3n, which is several times larger than the general Turán bound and is tight at least for λ=27. © 2016, Springer Science+Business Media New York.

Added: Oct 6, 2016
Article
Arias-Castro E., Le Gouic T. Discrete and Computational Geometry. 2019. P. 1-28.

We study shortest paths and their distances on a subset of a Euclidean space, and their approximation by their equivalents in a neighborhood graph defined on a sample from that subset. In particular, we recover and extend the results of Bernstein et al. (Graph approximations to geodesics on embedded manifolds, Tech. Rep., Department of Psychology, Stanford University, 2000). We do the same with curvature-constrained shortest paths and their distances, establishing what we believe are the first approximation bounds for them.

Added: May 12, 2019