23 citations · 51 across the 18 of their papers we have counts for
19 papers
An analogue of a theorem of Steinitz for ball polyhedra in
Sami Mezal Almohammad, Márton Naszódi, Zsolt Lángi
Steinitz's theorem states that a graph is the edge-graph of a -dimensional convex polyhedron if and only if, is simple, plane and -connected. We prove an analogue of…
Covering convex bodies and the Closest Vector Problem
Márton Naszódi, Moritz Venzin
We present algorithms for the -approximate version of the closest vector problem for certain norms. The currently fastest algorithm (Dadush and Kun 2016) for general norms h…
The Alon--Milman Theorem for non-symmetric bodies
Marton Naszodi
A classical theorem of Alon and Milman states that any dimensional centrally symmetric convex body has a projection of dimension which is either clos…
On contact graphs of totally separable packings in low dimensions
Károly Bezdek, Márton Naszódi
The contact graph of a packing of translates of a convex body in Euclidean -space is the simple graph whose vertices are the members of the packing, and whose two…
Arrangements of homothets of a convex body II
Márton Naszódi, Konrad J. Swanepoel
A family of homothets of an o-symmetric convex body K in d-dimensional Euclidean space is called a Minkowski arrangement if no homothet contains the center of any other homothet in…
Approximating a convex body by a polytope using the epsilon-net theorem
Márton Naszódi
Giving a joint generalization of a result of Brazitikos, Chasapis and Hioni and results of Giannopoulos and Milman, we prove that roughly $\left\lceil \frac{d}{(1-\vartheta)^d}\ln\…
On the Existence of Ordinary Triangles
Radoslav Fulek, Hossein Nassajian Mojarrad, Márton Naszódi +3
Let be a finite point set in the plane. A \emph{-ordinary triangle} in is a subset of consisting of three non-collinear points such that each of the three lines dete…
The Kneser--Poulsen conjecture for special contractions
Károly Bezdek, Márton Naszódi
The Kneser--Poulsen Conjecture states that if the centers of a family of unit balls in is contracted, then the volume of the union (resp., intersection) does no…
Bounding a global red-blue proportion using local conditions
Márton Naszódi, Leonardo Martínez-Sandoval, Shakhar Smorodinsky
We study the following local-to-global phenomenon: Let and be two finite sets of (blue and red) points in the Euclidean plane . Suppose that in each "neighbor…
Approximating set multi-covers
Márton Naszódi, Alexandr Polyanskii
Johnson and Lovász and Stein proved independently that any hypergraph satisfies , where is the transversal number, is its fractional version…
Coverings: variations on a result of Rogers and on the Epsilon-net theorem of Haussler and Welzl
Nóra Frankl, János Nagy, Márton Naszódi
We consider four problems. Rogers proved that for any convex body , we can cover by translates of of density very roughly . First, we extend this res…
Separation with restricted families of sets
Zsolt Lángi, Márton Naszódi, János Pach +2
Given a finite -element set , a family of subsets is said to separate if any two elements of are separated by at least one member of $\mathc…
Proof of a conjecture of Bárány, Katchalski and Pach
Marton Naszodi
Bárány, Katchalski and Pach proved the following quantitative form of Helly's theorem. If the intersection of a family of convex sets in is of volume one, then the i…
Spindle Starshaped Sets
Karoly Bezdek, Marton Naszodi
In this paper, spindle starshaped sets are introduced and investigated, which apart from normalization form an everywhere dense subfamily within the family of starshaped sets. We f…
Ball-Polyhedra
Karoly Bezdek, Zsolt Langi, Marton Naszodi +1
We study two notions. One is that of spindle convexity. A set of circumradius not greater than one is spindle convex if, for any pair of its points, it contains every short circula…
Ball and Spindle Convexity with respect to a Convex Body
Zsolt Lángi, Márton Naszódi, István Talata
Let be a convex body. We introduce two notions of convexity associated to C. A set is -ball convex if it is the intersection of translates of , o…
Rigid ball-polyhedra in Euclidean 3-space
Karoly Bezdek, Marton Naszodi
A ball-polyhedron is the intersection with non-empty interior of finitely many (closed) unit balls in Euclidean 3-space. One can represent the boundary of a ball-polyhedron as the…
On the Transversal Number and VC-Dimension of Families of Positive Homothets of a Convex Body
Márton Naszódi, Steven Taschuk
Let F be a family of positive homothets (or translates) of a given convex body K in R^n. We investigate two approaches to measuring the complexity of F. First, we find an upper bou…
On the Constant of Homothety for Covering a Convex Set with Its Smaller Copies
Marton Naszodi
Let denote the smallest integer such that for every convex body in there is a such that is covered by translates of . In the book \emph{R…