Márton Naszódi,Moritz Venzin
Márton Naszódi
We present algorithms for the ( 1 + ϵ ) -approximate version of the closest vector problem for certain norms. The currently fastest algorithm (Dadush and Kun 2016) for general norms in dimension n has running time of 2 O ( n ) ( 1 ...
Two Remarks on Graph Norms [0.03%]
图范式的两点评论
Frederik Garbe,Jan Hladký,Joonkyung Lee
Frederik Garbe
For a graph H, its homomorphism density in graphs naturally extends to the space of two-variable symmetric functions W in L p , p ≥ e ( H ) , denoted by t(H, W). One may then define corresponding functionals ‖ W ‖ H :...
Clément Berenfeld,John Harvey,Marc Hoffmann et al.
Clément Berenfeld et al.
The reach of a submanifold is a crucial regularity parameter for manifold learning and geometric inference from point clouds. This paper relates the reach of a submanifold to its convexity defect function. Using the stability properties of ...
Stefan Felsner,Alexander Pilz,Patrick Schnider
Stefan Felsner
We consider arrangements of n pseudo-lines in the Euclidean plane where each pseudo-line ℓ i is represented by a bi-infinite connected x-monotone curve f i ( x ) , x ∈ R , such that for any two pseudo-lines ℓ i and &...
István Tomon
István Tomon
A string graph is the intersection graph of curves in the plane. We prove that for every ϵ > 0 , if G is a string graph with n vertices such that the edge density of G is below 1 / 4 - ϵ , then V(G) contains two linear sized s...
Giulia Codenotti,Francisco Santos,Matthias Schymura
Giulia Codenotti
We explore upper bounds on the covering radius of non-hollow lattice polytopes. In particular, we conjecture a general upper bound of d/2 in dimension d, achieved by the "standard terminal simplices" and direct sums of them. We prove this c...
Number of Directions Determined by a Set in [Formula: see text] and Growth in [Formula: see text] [0.03%]
集合在[公式: 见文本]中确定的方向数以及在[公式: 见文本]中的增长数量
Daniele Dona
Daniele Dona
We prove that a set A of at most q non-collinear points in the finite plane F q 2 spans more than | A | / q directions: this is based on a lower bound by Fancsali et al. which we prove again together with a different upper bound than t...
Patricia Cahn,Alexandra Kjuchukova
Patricia Cahn
Let M be a connected, closed, oriented three-manifold and K, L two rationally null-homologous oriented simple closed curves in M. We give an explicit algorithm for computing the linking number between K and L in terms of a presentation of M...
Randomized Incremental Construction of Delaunay Triangulations of Nice Point Sets [0.03%]
宜定点集的Delaunay三角剖分的随机增量构造
Jean-Daniel Boissonnat,Olivier Devillers,Kunal Dutta et al.
Jean-Daniel Boissonnat et al.
Randomized incremental construction (RIC) is one of the most important paradigms for building geometric data structures. Clarkson and Shor developed a general theory that led to numerous algorithms which are both simple and efficient in the...
Herbert Edelsbrunner,Georg Osang
Herbert Edelsbrunner
Given a locally finite X ⊆ R d and a radius r ≥ 0 , the k-fold cover of X and r consists of all points in R d that have k or more points of X within distance r. We consider two filtrations-one in scale obtained by fixing k ...