Journal: Discrete Mathematics & Theoretical Computer Science

Abbreviation

Discret. math. theor. comput. sci.

Publisher

LORIA

Journal Volumes

ISSN

1365-8050
1462-7264

Description

Filters

Reset filters

Search Results

Publications 1 - 5 of 5
  • Properties of Random Graphs via Boltzmann Samplers
    Item type: Conference Paper
    Panagiotou, Konstantinos; Weissl, Andreas (2008)
    Discrete Mathematics & Theoretical Computer Science ~ 2007 Conference on Analysis of Algorithms, AofA 07
  • Cell-Paths in Mono- and Bichromatic Line Arrangements in the Plane
    Item type: Journal Article
    Aichholzer, Oswin; Cardinal, Jean; Hackl, Thomas; et al. (2014)
    Discrete Mathematics & Theoretical Computer Science
  • Relaxed Two-Coloring of Cubic Graphs
    Item type: Conference Paper
    Berke, Robert; Szabó, Tibor (2005)
    Discrete Mathematics & Theoretical Computer Science
  • On the VC-dimension of half-spaces with respect to convex sets
    Item type: Journal Article
    Grelier, Nicolas; Miltzow, Tillmann; Ilchi, Saeed Gh.; et al. (2021)
    Discrete Mathematics & Theoretical Computer Science
    A family S of convex sets in the plane defines a hypergraph H = (S, epsilon) with S as a vertex set and epsilon as the set of hyperedges as follows. Every subfamily S' subset of S defines a hyperedge in epsilon if and only if there exists a halfspace h that fully contains S', and no other set of S is fully contained in h. In this case, we say that h realizes S'. We say a set S is shattered, if all its subsets are realized. The VC-dimension of a hypergraph H is the size of the largest shattered set. We show that the VC-dimension for pairwise disjoint convex sets in the plane is bounded by 3, and this is tight. In contrast, we show the VC-dimension of convex sets in the plane (not necessarily disjoint) is unbounded. We provide a quadratic lower bound in the number of pairs of intersecting sets in a shattered family of convex sets in the plane. We also show that the VC-dimension is unbounded for pairwise disjoint convex sets in R-d, for d >= 3. We focus on, possibly intersecting, segments in the plane and determine that the VC-dimension is at most 5. And this is tight, as we construct a set of five segments that can be shattered. We give two exemplary applications. One for a geometric set cover problem and one for a range-query data structure problem, to motivate our findings.
  • Tight Bounds for Delay-Sensitive Aggregation
    Item type: Journal Article
    Pignolet, Yvonne Anne; Schmid, Stefan; Wattenhofer, Roger (2010)
    Discrete Mathematics & Theoretical Computer Science
Publications 1 - 5 of 5