Separation by Convex Pseudo-Circles
Separation by Convex Pseudo-Circles
复制标题
通过凸伪圆进行分离
DOI：
10.1145/2582112.2582148
复制
发表时间：
2014
影响因子：
0.8
通讯作者：
J. Spehner
中科院分区：
文献类型：
--
作者：
N. Chevallier;A. Fruchard;Dominique Schmitt;J. Spehner
Let S be a finite set of n points in the plane in general position. We prove that every inclusion-maximal family of subsets of S separable by convex pseudo-circles has the same cardinal n0+n1+n2+n3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\left( {\begin{array}{c}n\\ 0\end{array}}\right) +\left( {\begin{array}{c}n\\ 1\end{array}}\right) +\left( {\begin{array}{c}n\\ 2\end{array}}\right) +\left( {\begin{array}{c}n\\ 3\end{array}}\right) $$\end{document}. This number does not depend on the configuration of S and is the same as the number of subsets of S separable by true circles. For a fixed k∈{1,⋯,n-1}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \in \{1,\dots ,n-1\}$$\end{document}, we also count the number of elements in a maximal family of k-subsets of S separable by convex pseudo-circles. This time the number depends on the configuration of S, but it is again equal to the number of k-subsets of S separable by true circles. Thus, it is an invariant of S: it does not depend on the choice of the maximal family. To achieve these results, we introduce a graph that generalizes the dual graph of the order-k Voronoi diagram. The vertices of the graph are the elements of a maximal family of k-subsets of S separable by convex pseudo-circles. In order to count the number of these vertices, we show that the graph is realizable as a triangulation.
Let S be a finite set of n points in the plane in general position. We prove that every inclusion-maximal family of subsets of S separable by convex pseudo-circles has the same cardinal n0+n1+n2+n3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\left( {\begin{array}{c}n\\ 0\end{array}}\right) +\left( {\begin{array}{c}n\\ 1\end{array}}\right) +\left( {\begin{array}{c}n\\ 2\end{array}}\right) +\left( {\begin{array}{c}n\\ 3\end{array}}\right) $$\end{document}. This number does not depend on the configuration of S and is the same as the number of subsets of S separable by true circles. For a fixed k∈{1,⋯,n-1}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \in \{1,\dots ,n-1\}$$\end{document}, we also count the number of elements in a maximal family of k-subsets of S separable by convex pseudo-circles. This time the number depends on the configuration of S, but it is again equal to the number of k-subsets of S separable by true circles. Thus, it is an invariant of S: it does not depend on the choice of the maximal family. To achieve these results, we introduce a graph that generalizes the dual graph of the order-k Voronoi diagram. The vertices of the graph are the elements of a maximal family of k-subsets of S separable by convex pseudo-circles. In order to count the number of these vertices, we show that the graph is realizable as a triangulation.