Density of range capturing hypergraphs

DOI10.20382/JOCG.V7I1A1MaRDI QIDQ2970441zbMATH OpenOpenAlexFDO

Authors Torsten Ueckerdt, Maria Axenovich

Publication date 30 March 2017

Full work available at URL https://arxiv.org/abs/1404.1298

Hypergraphs (05C65) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35)

Abstract: For a finite set

X

of points in the plane, a set

S

in the plane, and a positive integer

k

, we say that a

k

-element subset

Y

of

X

is captured by

S

if there is a homothetic copy

S^{'}

of

S

such that

X c a p S^{'} = Y

, i.e.,

S^{'}

contains exactly

k

elements from

X

. A

k

-uniform

S

-capturing hypergraph

H = H (X, S, k)

has a vertex set

X

and a hyperedge set consisting of all

k

-element subsets of

X

captured by

S

. In case when

k = 2

and

S

is convex these graphs are planar graphs, known as convex distance function Delaunay graphs. In this paper we prove that for any

k g e q 2

, any

X

, and any convex compact set

S

, the number of hyperedges in

H (X, S, k)

is at most

(2 k - 1) | X | - k^{2} + 1 - s u m_{i = 1}^{k - 1} a_{i}

, where

a_{i}

is the number of

i

-element subsets of

X

that can be separated from the rest of

X

with a straight line. In particular, this bound is independent of

S

and indeed the bound is tight for all "round" sets

S

and point sets

X

in general position with respect to

S

. This refines a general result of Buzaglo, Pinchasi and Rote stating that every pseudodisc topological hypergraph with vertex set

X

has

O (k^{2} | X |)

hyperedges of size

k

or less.

Recommendations

Cited in

(4)

This page was built for publication: Density of range capturing hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2970441)