Name
Abstract | ||
|---|---|---|
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 (n 0)+(n 1)+(n 2)+(n 3). 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. Buzaglo, Holzman, and Pinchasi already showed that it is an upper bound for the number of subsets separable by (non necessarily convex) pseudo-circles. In fact, we first count the number of elements in a maximal family of k-subsets of S separable by convex pseudo-circles, for a given k. From a well known result of Lee, when the set S has no four cocircular points, it admits 2kn − n − k2 + 1 − Σ k−1 i=1 a(i)(S) k-point subsets separable by true circles, where a(i) (S) is the number of i-sets of S. Here we show that this result still holds for convex pseudo-circles. In particular, this means that the number of k-subsets of S separable by a maximal family of convex pseudo-circles is an invariant of S: It does not depend on the choice of the maximal family. To prove this result, we introduce a graph that generalizes the dual graph of the order-k Voronoi diagram, and whose vertices are the k-subsets of S separable by a maximal family of convex pseudo-circles. In order to count the number of vertices of this graph, we first show that it admits a planar realization which is a triangulation. It turns out (but is not detailed in the present paper) that these triangulations are the centroid triangulations defined by Liu and Snoeyink. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1145/2582112.2582148 | Symposium on Computational Geometry 2013 |
Keywords | Field | DocType |
inclusion-maximal family,true circle,maximal family,cocircular point,convex pseudo-circles,dual graph,k-point subsets separable,finite set,subsets separable,n point | Discrete mathematics,Family of sets,General position,Combinatorics,Vertex (geometry),Separable space,Convex set,Dual graph,Voronoi diagram,Invariant (mathematics),Mathematics | Conference |
Citations | PageRank | References |
1 | 0.37 | 9 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nicolas Chevallier | 1 | 8 | 2.27 |
| Augustin Fruchard | 2 | 1 | 1.05 |
| Dominique Schmitt | 3 | 19 | 7.47 |
| Jean-Claude Spehner | 4 | 76 | 12.15 |