Geodesic
Lower bounds for the number of hyperplanes separating two finite sets of points
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 20 (2014) no. 2, pp. 210-222 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

We consider the $NP$-hard polyhedral separability problem for two subsets $A$ and $B$ of points in general position in $\mathbb R^d$ with the fewest number of hyperplanes in the sense of boolean functions from a given class $\Sigma$. Both deterministic and probabilistic lower bounds are obtained for this number for two different classes of functions $\Sigma$.
Keywords: $k$-polyhedral separability, boolean function, monochromatic island, combinatorial discrepancy. 
@article{TIMM_2014_20_2_a16,
     author = {K. S. Kobylkin},
     title = {Lower bounds for the number of hyperplanes separating two finite sets of points},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {210--222},
     year = {2014},
     volume = {20},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2014_20_2_a16/}
}
TY  - JOUR
AU  - K. S. Kobylkin
TI  - Lower bounds for the number of hyperplanes separating two finite sets of points
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2014
SP  - 210
EP  - 222
VL  - 20
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/TIMM_2014_20_2_a16/
LA  - ru
ID  - TIMM_2014_20_2_a16
ER  - 
%0 Journal Article
%A K. S. Kobylkin
%T Lower bounds for the number of hyperplanes separating two finite sets of points
%J Trudy Instituta matematiki i mehaniki
%D 2014
%P 210-222
%V 20
%N 2
%U http://geodesic.mathdoc.fr/item/TIMM_2014_20_2_a16/
%G ru
%F TIMM_2014_20_2_a16
K. S. Kobylkin. Lower bounds for the number of hyperplanes separating two finite sets of points. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 20 (2014) no. 2, pp. 210-222. http://geodesic.mathdoc.fr/item/TIMM_2014_20_2_a16/

[1] Agarwal P., Suri S., “Surface approximation and geometric partitions”, Proc. of 5th ACM-SIAM symposium on Discrete algorithms (SODA'94), 1994, 24–33 | MR | Zbl

[2] Aronov B., Har-Peled S., “On approximating the depth and related problems”, SIAM J. Comput., 38:3 (2008), 899–921 | DOI | MR | Zbl

[3] Aurenhammer F., “Power diagrams: properties, algorithms, and applications”, SIAM J. Comput., 16:1 (1987), 78–96 | DOI | MR | Zbl

[4] Barany I., “A note on Sylvester's four-point problem”, Studia Sci. Math. Hungar., 38:1 (2001), 73–77 | MR | Zbl

[5] Barany I., “Sylvester's question: the probability that $n$ points are in convex position”, The Annals of Probability, 27:4 (1999), 2020–2034 | DOI | MR | Zbl

[6] Barany I., “Random points, convex bodies, lattices”, Proc. of the International Congress of Math., v. 3, 2002, 527–536 | MR

[7] Chlebus B., Nguyen S. H., “On finding optimal discretizations for two attributes”, Rough sets and current trends in computing (Warsaw, 1998), Lecture Notes in Comput. Sci., 1424, Springer, Berlin, 1998, 537–544 | DOI | MR

[8] Dumitrescu A., Pach J., “Partitioning colored point sets into monochromatic parts”, Algorithms and data structures (Providence, RI, USA, 2001), Lecture Notes in Comput. Sci., 2125, Springer, Berlin, 2001, 264–275 | DOI | MR | Zbl

[9] Edelsbrunner H., Algorithms in combinatorial geometry, Springer-Verlag, 1989, 423 pp. | MR

[10] Fischer P., “Sequential and parallel algorithms for finding a maximum convex polygon”, Comp. Geom., 7:3 (1997), 187–200 | DOI | MR | Zbl

[11] Hoeffding W., “Probability inequalities for sums of bounded random variables”, J. Amer. Statist. Assoc., 58:301 (1963), 13–30 | DOI | MR | Zbl

[12] Houle M. E., “Algorithms for weak and wide separation of sets”, Discrete Appl. Math., 45:2 (1993), 139–159 | DOI | MR | Zbl

[13] Khachay M. Yu., “On approximate algorithm for minimal committee of a system of linear inequalities”, Pattern Recognition and Image Analysis, 13:3 (2003), 459–464

[14] Khachay M. Yu., Poberii M. I., “Complexity and approximability of committee polyhedral separability of sets in general position”, Informatica, 20:2 (2009), 217–234 | MR | Zbl

[15] Kobylkin K.S., “Necessary condition for committee existence”, Pattern Recognition and Image Analysis, 12:1 (2002), 26–31

[16] Matousek J., Geometric discrepancy, An illustrated guide, Ser. Algorithms and Combinatorics, 18, Springer, Berlin, 1999, 288 pp. | DOI | MR | Zbl

[17] Megiddo N., “On the complexity of polyhedral separability”, Discrete Comput. Geom., 3:4 (1988), 325–337 | DOI | MR | Zbl

[18] Mitchell J., Suri S., “Separation and approximation of polyhedral surfaces”, Comp. Geom., 5:2 (1995), 95–114 | DOI | MR | Zbl

[19] Alon N., Spenser Dzh., Veroyatnostnyi metod, Binom, M., 2007, 320 pp.

[20] Geil D., “Sosednie vershiny na vypuklom mnogogrannike”, Lineinye neravenstva i smezhnye voprosy, Sb. st., eds. G. U. Kun, A. U. Takker, Izd-vo inostr. lit., M., 1959, 470 pp.

[21] Emelichev V. A., Kovalev M. M., Kravtsov M. K., Mnogogranniki, grafy, optimizatsiya, Nauka, M., 1981, 320 pp. | MR | Zbl

[22] Mazurov Vl. D., Khachai M. Yu., “Komitetnye konstruktsii”, Izv. Ural. gos. un-ta. Matematika i mekhanika, 1999, no. 2, 77–108 | MR | Zbl

[23] Mazurov Vl. D., Khachai M. Yu., “Busting i polinomialnaya approksimiruemost zadachi o minimalnom affinnom razdelyayuschem komitete”, Tr. In-ta matematiki i mekhaniki UrO RAN, 19, no. 2, 2013, 231–236

[24] Matsenov A. A., “Komitetnyi busting: minimizatsiya chisla bazovykh algoritmov pri prostom golosovanii”, Tr. Vseross. konf. MMRO-13, Maks-Press, M., 2007, 180–183