Главная

Dömötör Pálvölgyi

  1. Decomposition of Geometric Set Systems and Graphs.

    Пт, 09/24/2010 - 15:01 — SomNambul
    Authors: Dömötör Pálvölgyi
    Subjects: Combinatorics
    Abstract

    We study two decomposition problems in combinatorial geometry. The first part
    deals with the decomposition of multiple coverings of the plane. We say that a
    planar set is cover-decomposable if there is a constant m such that any m-fold
    covering of the plane with its translates is decomposable into two disjoint
    coverings of the whole plane. Pach conjectured that every convex set is
    cover-decomposable. We verify his conjecture for polygons. Moreover, if m is
    large enough, we prove that any m-fold covering can even be decomposed into k
    coverings.

  2. Consistent digital line segments.

    Втр, 09/14/2010 - 15:02 — SomNambul
    Authors: Miloš Stojaković, Dömötör Pálvölgyi, Tobias Christ
    Subjects: Discrete Mathematics
    Abstract

    We introduce a novel and general approach for digitalization of line segments
    in the plane that satisfies a set of axioms naturally arising from Euclidean
    axioms. In particular, we show how to derive such a system of digital segments
    from any total order on the integers. As a consequence, using a well-chosen
    total order, we manage to define a system of digital segments such that all
    digital segments are, in Hausdorff metric, optimally close to their
    corresponding Euclidean segments, thus giving an explicit construction that
    resolves the main question of Chun et al.

  3. Drawing planar graphs of bounded degree with few slopes.

    Ср, 09/08/2010 - 15:02 — SomNambul
    Authors: János Pach, Dömötör Pálvölgyi, Balázs Keszegh
    Subjects: Combinatorics
    Abstract

    We settle a problem of Dujmovi\'c, Eppstein, Suderman, and Wood by showing
    that there exists a function $f$ with the property that every planar graph $G$
    with maximum degree $d$ admits a drawing with noncrossing straight-line edges,
    using at most $f(d)$ different slopes. If we allow the edges to be represented
    by polygonal paths with {\em one} bend, then $2d$ slopes suffice. Allowing {\em
    two} bends per edge, every planar graph with maximum degree $d\ge 3$ can be
    drawn using segments of at most $\lceil d/2\rceil$ different slopes.

  4. Bin Packing via Discrepancy of Permutations.

    Ср, 07/14/2010 - 15:02 — SomNambul
    Authors: Dömötör Pálvölgyi, Friedrich Eisenbrand, Thomas Rothvoß
    Subjects: Discrete Mathematics
    Abstract

    A well studied special case of bin packing is the 3-partition problem, where
    n items of size >1/4 have to be packed in a minimum number of bins of capacity
    one. The famous Karmarkar-Karp algorithm transforms a fractional solution of a
    suitable LP relaxation for this problem into an integral solution that requires
    at most O(log n) additional bins.

  5. Vectors in a Box.

    Чт, 12/03/2009 - 16:01 — SomNambul
    Authors: Jiří Matoušek, Kevin Buchin, Robin A. Moser, Dömötör Pálvölgyi
    Subjects: Combinatorics
    Abstract

    For an integer d>=1, let tau(d) be the smallest integer with the following
    property: If v1,v2,...,vt is a sequence of t>=2 vectors in [-1,1]^d with
    v1+v2+...+vt in [-1,1]^d, then there is a subset S of {1,2,...,t} of indices,
    2<=|S|<=tau(d), such that \sum_{i\in S} vi is in [-1,1]^d. The quantity tau(d)
    was introduced by Dash, Fukasawa, and G\"unl\"uk, who showed that tau(2)=2,
    tau(3)=4, and tau(d)=Omega(2^d), and asked whether tau(d) is finite for all d.

Math-arch

RSS-материал