Isaac Scientific Publishing

Journal of Advances in Applied Mathematics

ε-Nets of Two Sets and Their Application to the Classification Problem

Download PDF (1092.3 KB) PP. 43 - 54 Pub. Date: January 1, 2017

DOI: 10.22606/jaam.2017.21004


  • Maria A. Ivanchuk*
    Department of Biological Physics and Medical Informatics, Bukovinian State Medical University, Ukraine
  • Igor V. Malyk
    Department of the System Analysis and Insurance and Financial Mathematics, Yuriy Fedkovych Chernivtsi National University, Ukraine


The separation algorithm of linear two sets using their ε-nets in the range space (Rd ,Hd ) is proposed in the paper. The algorithm is illustrated by two examples for normal and uniform distributions. The set of possible values of ε and its properties are considered in the manuscript.


Epsilon-nets, sets’ separation, linear classification


[1] Aronov B., Ezra E., Sharir M. “Small-size epsilon-nets for axis-parallel rectangles and boxes”, Symposium on Theory of Computing, 2009, P.P. 639–648

[2] Christopher J.C. Burges “A Tutorial on Support Vector Machines for Pattern Recognition”, Data Mining and Knowledge Discovery, 2(2), 1998, P.121–167.

[3] Embrechts P., Hofert M. A note on generalized inverses Mathematical Methods of Operations Research , 2013, 77(3), 423-432

[4] G?rtner B., Hoffmann M. Computational Geometry, cture %20notes.pdf

[5] Hausler S. VC Dimension. A Tutorial for the Course Computational Intelligence, CI

[6] Haussler D. and Welzl E. “Epsilon-nets and simplex range queries”, Discrete Comput. Geom., 1987, №2, P.P. 127–151

[7] Ivanchuk M. A. , Malyk I. V. “ Using ε -Nets for Linear Separation of Two Sets in a Euclidean Space Rd”, Cybernetics and Systems Analysis, Vol.51, Issue 6 (2015), P. 965-968.

[8] Ivanchuk Maria A., Malyk Igor V. “Building expert medical prognostic systems using Voronoi diagram”, Hindawi Publishing Corporation. - International Journal of Computational Mathematics, Volume 2015, Article ID 415146, 4 pages. – DOI 10.1155/2015/415146

[9] Ivanchuk Mariya A., Malyk Igor V. “Separation of convex hulls as a way for modeling of systems of prediction of complications in patients”, Journal of Automation and Information Sciences, 2015, Vol.47, Issue 4, P.78-84, DOI: 10.1615/JAutomatInfScien.v47.i4.80

[10] Kulkarni J., Govindarajan S. “New ε-Net Constructions”, Canadian Conference on Computational Geometry (CCCG), 2010, P.P.159-162

[11] Matousek J., Seidel R., Welzl E. “How to Net a Lot with Little:Small ε-Nets for Disks and Halfspaces” In Proc. sixth annual symposium on Computational geometry, P.P. 16–22, 1990

[12] Tucker H.G. “A Generalization of the Glivenko-Cantelli Theorem”, The Annals of Mathematical Statistics, Vol. 30, No. 3, Sep., 1959, pp. 828-830