Separating bichromatic polylines by fixed-angle minimal triangles

Document Type : Article

Authors

1 Department of Computer Engineering, North Tehran Branch, Islamic Azad University, Tehran, Iran

2 Department of Computer Engineering, Amirkabir University of Technology, Tehran, Iran

Abstract

Separation of desired objects from undesired ones is one of the most important issues in the computational geometry. It is tended to cover the desired objects by one or a couple of geometric shapes in a way that all of the desired objects are included by the covering shapes, while the undesired objects are excluded. We study separation of polylines by minimal triangles with a given fixed angle and present O(N log N)-time algorithm, where N is the number of all the desired and undesired polylines. By a minimal triangle, we mean a triangle in which all of its edges are tangential to the convex hull of the desired polylines. The motivation for studying this separation problem stems from that we need to separate bichromatic objects that are modeled by polylines not points in real life scenarios.

Keywords

References

References:
1. Seara, C. "On geometric separability", Ph.D. Thesis, Polytechnic University of Catalunya (2002).
2. Cristianini, N. and Taylor, J.S., An Introduction to Support Vector Machines and Other Kernel-Based Learning Methods, Cambridge University Press (2000).
3. Dobkin, D.P., Gunopulos, D., and Maass, W. "Computing the maximum bichromatic discrepancy, with applications to computer graphics and machine learning", Journal of Computer and System Sciences, 52(3), pp. 453-470 (1996). 
4. Duda, R.O., Hart, P.E., and Stork, D.G., Pattern Classification, John Wiley & Sons (2012).
5. Eckstein, J., Hammer, P.L., Liu, Y., et al. "The maximum box problem and its application to data analysis", Computational Optimization and Applications, 23(3), pp. 285-298 (2002).
6. Edmonds, J., Gryz, J., Liang, D., et al. "Mining for empty spaces in large data sets", Theoretical Computer Science, 296(3), pp. 435-452 (2003).
7. Megiddo, N. "Linear-time algorithms for linear programming in R3 and related problems", Society for Industrial and Applied Mathematics Journal on Computing, 12(4), pp. 759-776(1983).
8. Rourke, J.O., Kosaraju, S.R., and Megiddo, N. "Computing circular separability", Discrete and Computational Geometry, 1, pp. 105-113 (1986).
9. Edelsbrunner, H. and Preparata, F.P "Minimum polygonal separation", Information and Computation Journal, 77, pp. 218-232 (1988).
10. Fekete, S. "On the complexity of min-link red-blue separation", Manuscript, Department of Applied Mathematics, SUNY Stony Brook, NY (1992).
11. Mitchell, J.S.B. "Approximation algorithms for geometric separation problems", Technical Report, State University of New York at Stony Brook (1993).
12. Hurtado, F., Noy, M., Ramos, P.A., et al. "Separating objects in the plane with wedges and strips", Discrete Applied Mathematics, 109, pp. 109-138 (2001).
13. Sarkar, D. and Stojmenovic, I. "Parallel algorithms for separation of two sets of points and recognition of digital convex polygons", International Journal of Parallel Programing, 21, pp. 109-121 (1992).
14. Eckstein, J., Hammer, P., Liu, Y., et al. "The maximum box problem and its application to data analysis", Computational Optimization and Applications, 23(3), pp. 85-98 (2002).
15. Liu, Y. and Nediak, M. "Planar case of the maximum box and related problems", 15th Canadian Conference of Computational Geometry, Eindhoven, Netherlands, pp. 14-18 (2003).
16. Demaine, E.D., Erickson, J., Hurtado, F., et al. "Separating point sets in polygonal environments", International Journal of Computational Geometry and Applications, 15(4), pp. 403-419 (2055).
17. Sheikhi, F., Mohades, A., de Berg, M., et al. "Separating bichoromatic point sets by L-shapes", Computational Geometry, 48(9), pp. 673-687 (2015).
18. Moslehi, Z. and Bagheri, A. "Separating bichoromatic point sets by disjoint isothetic rectangles", Scientia Iranica, Transaction D, Computer Science & Engineering, Electrical, 23(3), pp. 1228-1238 (2016).
19. Sheikhi, F., Mohades, A., Berg, B., et al. "Separability of imprecise points", Computational Geometry, 61, pp. 24-37 (2017).
20. Bandyapadhyay, S. and Banik, A. "Polynomial time algorithms for bichromatic problems", In 553 Conference on Algorithms and Discrete Applied Mathematics, pp. 12-23, Springer (2017).
21. Xue, J., Li, Y., and Janardan, R. "On the separability of stochastic geometric objects, with applications", Computational Geometry, 74, pp. 1-20 (2018).
22. Har-Peled, S. and Jones, M. "On separating points by lines", SODA '18: Symposium on Discrete Algorithms New Orleans Louisiana January, pp. 918-932 (2018).
23. Bonnet, E. and Lampis, M. "On the parameterized complexity of red-blue points separation", Journal of Computational Geometry, 10(1), pp. 181-206 (2019).
24. Abrahamsen, M., Giannopoulos, P., Loffler, M., et al. "The shortest separating cycle problem", Discrete & Computational Geometry, 64, pp. 575-607 (2020).
25. Arkin, E., Gao, J., Hesterberg, A., et al. "The shortest separating cycle problem", Proceedings of the 14th Workshop on Approximation and Online Algorithms (2017).
26. Misra, N., Mittal, H., and Sethia, A. "Red-blue point separation for points on a circle", 32th Canadian Conference of Computational Geometry, Saskatoon, Saskatchewan, pp. 266-272 (2020).
27. Acharyya, A., Minati, D., Nandy, S.C., et al. "Variationsof largest rectangle recognition amidst a bichromatic point set", Discrete Applied Mathematics, 286, pp. 35-50 (2020).
28. Moslehi, Z. and Bagheri, A. "Separating bichromatic point sets by minimal triangles", International Journal of Foundations of Computer Science, 28(4), pp. 309- 320 (2017).
29. Welz, W. "Smallest enclosing disks (balls ellipsoids)", Results and Trends in Computer Science, Springer- Verlag, Austria, pp. 359-370 (1991).
30. Teichman, M. "Shoving a table into a corner", Tech. Report SOCS-88.11, Computational Geometry Laboratory, McGill University, pp. 99-118 (1988).
31. vanKreveld, M., van Lankveld, T., and Veltkamp, R. "Identifying well-covered minimal bounding rectangles in 2D point data", In 25th European Workshop on Computational Geometry, pp. 277-280 (2009).
Scientia Iranica
Volume 29, Issue 5
Transactions on Computer Science & Engineering and Electrical Engineering (D)
September and October 2022
Pages 2405-2417

Files

History

  • Receive Date: 07 October 2021
  • Revise Date: 07 February 2022
  • Accept Date: 25 April 2022

Share

How to cite

Statistics