文章基本信息

标题：Weak 1/r-Nets for Moving Points
本地全文：下载
作者：Alexandre Rok ; Shakhar Smorodinsky
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：51
页码：59:1-59:13
DOI：10.4230/LIPIcs.SoCG.2016.59
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：In this paper, we extend the weak 1/r-net theorem to a kinetic setting where the underlying set of points is moving polynomially with bounded description complexity. We establish that one can find a kinetic analog N of a weak 1/r-net of cardinality O(r^(d(d+1)/2)log^d r) whose points are moving with coordinates that are rational functions with bounded description complexity. Moreover, each member of N has one polynomial coordinate.
关键词：Hypergraphs; Weak epsilon-net