Discrete & Computational Geometry

Items from 1 to 20 out of 44 results

article

Proof of a Conjecture of Bárány, Katchalski and Pach

Márton Naszódi

Discrete & Computational Geometry > 2016 > 55 > 1 > 243-248

Bárány, Katchalski and Pach (Proc Am Math Soc 86(1):109–114, 1982) (see also Bárány et al., Am Math Mon 91(6):362–365, 1984) proved the following quantitative form of Helly’s theorem. If the intersection of a family of convex sets in $$\mathbb {R}^d$$ R d is of volume one, then the intersection of some subfamily of at most 2d members is of volume at most some constant v(d). In Bárány...

article

Persistence Modules on Commutative Ladders of Finite Type

Emerson G. Escolar, Yasuaki Hiraoka

Discrete & Computational Geometry > 2016 > 55 > 1 > 100-157

We study persistence modules defined on commutative ladders. This class of persistence modules frequently appears in topological data analysis, and the theory and algorithm proposed in this paper can be applied to these practical problems. A new algebraic framework deals with persistence modules as representations on associative algebras and the Auslander–Reiten theory is applied to develop the theoretical...

article

Recognition of Collapsible Complexes is NP-Complete

Martin Tancer

Discrete & Computational Geometry > 2016 > 55 > 1 > 21-38

We prove that it is NP-complete to decide whether a given (3-dimensional) simplicial complex is collapsible. This work extends a result of Malgouyres and Francés showing that it is NP-complete to decide whether a given simplicial complex collapses to a 1-complex.

article

Optimal Packings of Congruent Circles on a Square Flat Torus

Oleg R. Musin, Anton V. Nikitenko

Discrete & Computational Geometry > 2016 > 55 > 1 > 1-20

We consider packings of congruent circles on a square flat torus, i.e., periodic (w.r.t. a square lattice) planar circle packings, with the maximal circle radius. This problem is interesting due to a practical reason—the problem of “super resolution of images.” We have found optimal arrangements for $$N=6$$ N = 6 , 7 and 8 circles. Surprisingly, for the case $$N=7$$ N = 7 there...

article

Geometric Realizations and Duality for Dahmen–Micchelli Modules and De Concini–Procesi–Vergne Modules

Francesco Cavazzani, Luca Moci

Discrete & Computational Geometry > 2016 > 55 > 1 > 74-99

We give an algebraic description of several modules and algebras related to the vector partition function, and we prove that they can be realized as the equivariant K-theory of some manifolds that have a nice combinatorial description. We also propose a more natural and general notion of duality between these modules, which corresponds to a Poincaré duality-type correspondence for equivariant K-theory.

article

On the Multiple Packing Densities of Triangles

Kirati Sriamorn

Discrete & Computational Geometry > 2016 > 55 > 1 > 228-242

Given a convex disk K and a positive integer k, let $$\delta _T^k(K)$$ δ T k ( K ) and $$\delta _L^k(K)$$ δ L k ( K ) denote the k-fold translative packing density and the k-fold lattice packing density of K, respectively. Let T be a triangle. In a very recent paper (Sriamorn 2014, http://arxiv.org/abs/1412.5096 ), I proved that $$\delta _L^k(T)=\frac{2k^2}{2k+1}$$...

article

Polynomial Partitioning on Varieties of Codimension Two and Point-Hypersurface Incidences in Four Dimensions

Saugata Basu, Martín Sombra

Discrete & Computational Geometry > 2016 > 55 > 1 > 158-184

We present a polynomial partitioning theorem for finite sets of points in the real locus of an irreducible complex algebraic variety of codimension at most two. This result generalizes the polynomial partitioning theorem on the Euclidean space of Guth and Katz, and its extension to hypersurfaces by Zahl and by Kaplan, Matoušek, Sharir and Safernová. We also present a bound for the number of incidences...

article

On the Complexity of the Set of Unconditional Convex Bodies

Mark Rudelson

Discrete & Computational Geometry > 2016 > 55 > 1 > 185-202

We show that for any $$1 \le t \le \tilde{c} n^{1/2} \log ^{-5/2} n$$ 1 ≤ t ≤ c ~ n 1 / 2 log - 5 / 2 n , the set of unconditional convex bodies in $$\mathbb {R}^n$$ R n contains a t-separated subset of cardinality at least $$\begin{aligned} \exp \Big (\exp \Big (\frac{c}{t^2 \log ^4 (1+t)} \, n \Big ) \Big ). \end{aligned}$$ exp ( exp ( c t 2 log...

article

How to Walk Your Dog in the Mountains with No Magic Leash

Sariel Har-Peled, Amir Nayyeri, Mohammad Salavatipour, Anastasios Sidiropoulos

Discrete & Computational Geometry > 2016 > 55 > 1 > 39-73

We describe a $$O(\log n )$$ O ( log n ) -approximation algorithm for computing the homotopic Fréchet distance between two polygonal curves that lie on the boundary of a triangulated topological disk. Prior to this work, algorithms were known only for curves on the Euclidean plane with polygonal obstacles. A key technical ingredient in our analysis is a $$O(\log n)$$ O ( log n ) ...

article

Cayley Factorization and the Area Principle

Susanne Apel

Discrete & Computational Geometry > 2016 > 55 > 1 > 203-227

In Sturmfels and Whiteley (J Symb Comput 11(5):439–453, 1991), it is proven that any multihomogenous bracket polynomial with integer coefficients can be interpreted by a ruler construction when introducing simple non-degeneracy conditions. This problem is called (generalized) Cayley factorization. This allows for geometrically interpreting many projective invariant properties. We reprove the above...

article

How to Guard Orthogonal Polygons: Diagonal Graphs and Vertex Covers

T. S. Michael, Val Pinciu

Discrete & Computational Geometry > 2016 > 55 > 2 > 410-422

We extend and unify most known results about guarding orthogonal polygons by introducing the same-sign diagonal graphs of a convex quadrangulation and applying results about vertex covers for graphs. Our approach also yields new theorems and often guarantees two disjoint vertex guard sets of relatively small cardinality. For instance, an orthogonal polygon on n vertices has two disjoint vertex guard...

article

The Edit Distance for Reeb Graphs of Surfaces

Barbara Di Fabio, Claudia Landi

Discrete & Computational Geometry > 2016 > 55 > 2 > 423-461

Reeb graphs are structural descriptors that capture shape properties of a topological space from the perspective of a chosen function. In this work, we define a combinatorial distance for Reeb graphs of orientable surfaces in terms of the cost necessary to transform one graph into another by edit operations. The main contributions of this paper are the stability property and the optimality of this...

article

Discrete Optimal Transport: Complexity, Geometry and Applications

Quentin Mérigot, Édouard Oudet

Discrete & Computational Geometry > 2016 > 55 > 2 > 263-283

In this article, we introduce a new algorithm for solving discrete optimal transport based on iterative resolutions of local versions of the dual linear program. We show a quantitative link between the complexity of this algorithm and the geometry of the underlying measures in the quadratic Euclidean case. This discrete method is then applied to investigate two optimal transport problems with geometric...

article

Two-Orbit Convex Polytopes and Tilings

Nicholas Matteo

Discrete & Computational Geometry > 2016 > 55 > 2 > 296-313

We classify the convex polytopes whose symmetry groups have two orbits on the flags. These exist only in two or three dimensions, and the only ones whose combinatorial automorphism group is also two-orbit are the cuboctahedron, the icosidodecahedron, and their duals. The combinatorially regular two-orbit convex polytopes are certain 2n-gons for each $$n \ge 2$$ n ≥ 2 . We also classify the...

article

Gain-Sparsity and Symmetry-Forced Rigidity in the Plane

Tibor Jordán, Viktória E. Kaszanitzky, Shin-ichi Tanigawa

Discrete & Computational Geometry > 2016 > 55 > 2 > 314-372

We consider planar bar-and-joint frameworks with discrete point group symmetry in which the joint positions are as generic as possible subject to the symmetry constraint. We provide combinatorial characterizations for symmetry-forced rigidity of such structures with rotation symmetry or dihedral symmetry of order 2k with odd k, unifying and extending previous work on this subject. We also explore...

article

Combining Persistent Homology and Invariance Groups for Shape Comparison

Patrizio Frosini, Grzegorz Jabłoński

Discrete & Computational Geometry > 2016 > 55 > 2 > 373-409

Persistent homology has proven itself quite efficient in the topological and qualitative comparison of filtered topological spaces, when invariance with respect to every homeomorphism is required. However, we can make the following two observations about the use of persistent homology for application purposes. On the one hand, more restricted kinds of invariance are sometimes preferable (e.g., in...

article

A $$t_k$$ t k Inequality for Arrangements of Pseudolines

I. N. Shnurnikov

Discrete & Computational Geometry > 2016 > 55 > 2 > 284-295

Consider arrangements of n pseudolines in the real projective plane. Let $$t_k$$ t k denote the number of intersection points where exactly k pseudolines are incident. We present a new combinatorial inequality: $$\begin{aligned} t_2+1.5t_3\ge 8+\sum _{k\ge 4}(2k-7.5)t_k, \end{aligned}$$ t 2 + 1.5 t 3 ≥ 8 + ∑ k ≥ 4 ( 2 k - 7.5 ) t k , which holds if no more...

article

Gap Probabilities and Betti Numbers of a Random Intersection of Quadrics

Antonio Lerario, Erik Lundberg

Discrete & Computational Geometry > 2016 > 55 > 2 > 462-496

We consider the Betti numbers of an intersection of k random quadrics in $$\mathbb {R}\text {P}^n$$ R P n . Sampling the quadrics independently from the Kostlan ensemble, as $$n \rightarrow \infty $$ n → ∞ we show that for each $$i\ge 0$$ i ≥ 0 the expected ith Betti number satisfies $$\begin{aligned} \mathbb {E}b_i(X)=1+O(n^{-M})\quad \text {for all } M>0...

article

The Filling Problem in the Cube

Dominic Dotterrer

Discrete & Computational Geometry > 2016 > 55 > 2 > 249-262

We prove an isoperimetric inequality for filling cellular $$\mathbb {Z}_2$$ Z 2 -cycles in a high-dimensional cube with cellular chains. In addition, we provide a family of cubical cellular cycles for which the exponent in the inequality is optimal.

article

Better Bounds for Planar Sets Avoiding Unit Distances

Tamás Keleti, Máté Matolcsi, Fernando Mário Oliveira Filho, Imre Z. Ruzsa

Discrete & Computational Geometry > 2016 > 55 > 3 > 642-661

A 1-avoiding set is a subset of $$\mathbb {R}^n$$ R n that does not contain pairs of points at distance 1. Let $$m_1(\mathbb {R}^n)$$ m 1 ( R n ) denote the maximum fraction of $$\mathbb {R}^n$$ R n that can be covered by a measurable 1-avoiding set. We prove two results. First, we show that any 1-avoiding set in $$\mathbb {R}^n (n\ge 2)$$ R n...

Volume:
55
Year:
2016

Publication date

Set your own date range

Number

4 (11)
3 (14)
2 (9)
1 (10)

Keywords

CONVEX POLYTOPES (4)
COMBINATORIAL GEOMETRY (3)
BANACH–MAZUR DISTANCE (2)
DELAUNAY TRIANGULATION (2)
HALF-REGULAR (2)
INCIDENCE GEOMETRY (2)
LINEAR PROGRAMMING (2)
POLYNOMIAL PARTITIONING (2)
QUASIREGULAR (2)
TILINGS (2)
TWO-ORBIT (2)
F-VECTOR (1)
G-THEOREM (1)
K-TREE (1)
$$T K$$ T K INEQUALITIES FOR ARRANGEMENTS OF LINES (1)
ABSTRACT POLYTOPE (1)
ALEXANDROV PROBLEM (1)
APOLLONIAN BALL PACKING (1)
APPROXIMATION ALGORITHMS (1)
APPROXIMATION BY POLYTOPES (1)
ART GALLERY THEOREM (1)
AUSLANDER–REITEN THEORY (1)
BANG’S PROBLEM (1)
BETTI NUMBERS (1)
BING’S HOUSE (1)
BRACKET POLYNOMIALS (1)
BRUNN–MINKOWSKI INEQUALITY (1)
CAYLEY FACTORIZATION (1)
CELL DECOMPOSITION (1)
CHROMATIC NUMBER OF EUCLIDEAN SPACE (1)
CIRCLE PACKING (1)
COLLAPSIBILITY (1)
COLORING OF THE PLANE (1)
COMBINATORIAL COMPLEXITY (1)
COMMUTATIVE LADDER (1)
CONNECTED COMPONENTS OF SEMI-ALGEBRAIC SETS (1)
CONTACT GRAPH (1)
CONVEX BODY (1)
CONVEX SETS IN THE PLANE (1)
COSHEAF (1)
COVERING BY CYLINDERS (1)
COVERING SPACE (1)
CROSSING SPANS LEMMA (1)
CRYSTALLOGRAPHIC GROUPS (1)
CYCLIC PERMUTATIONS (1)
DAHMEN-MICCHELLI (1)
DENSITY (1)
DIAMETER (1)
DISCRETE GEOMETRY (1)
DISTANCE-AVOIDING SETS (1)
DVORETZKY–ROGERS LEMMA (1)
EHRHART THEORY (1)
ENUMERATIVE PROBLEMS (1)
EQUIVARIANT K-THEORY (1)
EQUIVELAR TOROID (1)
ERDŐS–SZEKERES PROBLEM (1)
EXTENDED CROSSING SPANS LEMMA (1)
FILTERING FUNCTION (1)
FLAGS (1)
FLAT TORUS (1)
FORBIDDEN SUBGRAPH (1)
FRACTIONAL COLORING (1)
FRAME MATROIDS (1)
FRAMEWORKS (1)
FRÉCHET DISTANCE (1)
GAP PROBABILITY (1)
GEOMETRIC CONFIGURATIONS (1)
GEOMETRIC REALIZATION (1)
GEOMETRIC SET SYSTEMS (1)
GEOMETRIC TREE GRAPHS (1)
GRAPH EDIT DISTANCE (1)
GRAPH ENUMERATION (1)
GRASSMANN–CAYLEY ALGEBRA (1)
GROUP ACTION (1)
GROUP-LABELED GRAPHS (1)
HADWIGER–NELSON PROBLEM (1)
HARMONIC ANALYSIS (1)
HELLY’S THEOREM (1)
HIGH-DIMENSIONAL GEOMETRY (1)
HILBERT FUNCTIONS (1)
HOMOTOPY HEIGHT (1)
IMPLEMENTATION (1)
INCREMENTAL ALGORITHM (1)
INFINITESIMAL RIGIDITY (1)
INSCRIBED POLYTOPE (1)
INTERLACEMENT GRAPH (1)
INTERLEAVING DISTANCE (1)
INTERSECTION OF CONVEX SETS (1)
ISOPERIMETRY (1)
JOHN’S ELLIPSOID (1)
LATTICE POLYTOPE (1)
LOCAL COMPLEMENTATION (1)
MINKOWSKI SUM (1)
MORSE FUNCTION (1)
MOVABLE CONFIGURATIONS (1)
MULTIPLE PACKING (1)
MULTIPLE POINTS OF IMMERSIONS (1)
NATURAL PSEUDO-DISTANCE (1)
NATURAL STRATIFICATION (1)
NON-CROSSING RAYS CONFIGURATIONS (1)
more

INFONA - science communication portal

Discrete & Computational Geometry

Proof of a Conjecture of Bárány, Katchalski and Pach

Persistence Modules on Commutative Ladders of Finite Type

Recognition of Collapsible Complexes is NP-Complete

Optimal Packings of Congruent Circles on a Square Flat Torus

Geometric Realizations and Duality for Dahmen–Micchelli Modules and De Concini–Procesi–Vergne Modules

On the Multiple Packing Densities of Triangles

Polynomial Partitioning on Varieties of Codimension Two and Point-Hypersurface Incidences in Four Dimensions

On the Complexity of the Set of Unconditional Convex Bodies

How to Walk Your Dog in the Mountains with No Magic Leash

Cayley Factorization and the Area Principle

How to Guard Orthogonal Polygons: Diagonal Graphs and Vertex Covers

The Edit Distance for Reeb Graphs of Surfaces

Discrete Optimal Transport: Complexity, Geometry and Applications

Two-Orbit Convex Polytopes and Tilings

Gain-Sparsity and Symmetry-Forced Rigidity in the Plane

Combining Persistent Homology and Invariance Groups for Shape Comparison

A $$t_k$$ t k Inequality for Arrangements of Pseudolines

Gap Probabilities and Betti Numbers of a Random Intersection of Quadrics

The Filling Problem in the Cube

Better Bounds for Planar Sets Avoiding Unit Distances

Filter options

Publication date

Number

Keywords

INFONA - science communication portal

Discrete & Computational Geometry

Add recipient

Sending message cancelled

Are you sure you want to cancel sending this message?

Send message

Filter options

Publication date

Date range setting

Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.

Number

Keywords

Reporting an error / abuse

Sending the report failed

Accessibility options