Separating bichromatic point sets by minimal triangles with a fixed angle. (English) Zbl 1372.68268
Summary: Given a set \(P\) of red points and a set \(Q\) of blue points in the plane, of total size \(n\), we investigate the problem of finding triangles with a given angle \(\theta\) that (a) contain all points of \(Q\), (b) avoid all points of \(P\), and (c) are minimal, i.e. their three sides are tangent to the convex hull of \(Q\). Such triangles are called minimal separating \(\theta\)-triangles. We give an algorithm for reporting all combinatorially different minimal separating \(\theta\)-triangles in \(O(n\log n)\) time.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
Keywords:
computational geometry; point set; enclosing problem; separability problem; bichromatic; triangleReferences:
| [1] | Arkin, E. M., Hurtado, F., Mitchell, J. S. B., Seara, C. and Skiena, S., Some lower bounds on geometric separability problems, Int. J. Comput. Geom. Appl.16 (2006) 1-26. · Zbl 1093.68042 |
| [2] | Bhattacharya, B. K. and Mukhopadhyay, A., On the minimum perimeter triangle enclosing a convex polygon, Discrete and Computational Geometry (Springer, Berlin, 2003), pp. 84-96. · Zbl 1179.52012 |
| [3] | Bose, P. and De Carufel, J. L., Minimum-area enclosing triangle with a fixed angle, Comput. Geom.47 (2014) 90-109. · Zbl 1287.65012 |
| [4] | Bose, P., Seara, C. and Sethia, S., On computing enclosing isosceles triangles and related problems, Int. J. Comput. Geom. Appl.21 (2011) 25-45. · Zbl 1221.65058 |
| [5] | Dobkin, D. P. and Gunopulos, D., Geometric problems in machine learning, Applied Computational Geometry Towards Geometric Engineering (Springer, Berlin, 1996), pp. 121-132. · Zbl 1541.68315 |
| [6] | Edelsbrunner, H. and Preparata, F., Minimum polygonal separation, Inf. Comput.77 (1988) 218-232. · Zbl 0642.52004 |
| [7] | S. Fekete, On the complexity of min-link red-blue separation, manuscript, Department of Applied Mathematics, SUNY Stony Brook, NY (1992). |
| [8] | Klee, V. and Laskowski, M. C., Finding the smallest triangles containing a given convex polygon, J. Algoritm.6 (1985) 359-375. · Zbl 0577.52003 |
| [9] | van Kreveld, M., van Lankveld, T. and Veltkamp, R., Identifying well-covered minimal bounding rectangles in 2D point data, Proc. 25th Eur. Workshop on Comput. Geom., Belgium, (2009), pp. 277-280. |
| [10] | Megiddo, N., Linear-time algorithms for linear programming in \(\mathbb{R}^3\) and related problems, SIAM J. Comput.12 (1983) 759-776. · Zbl 0521.68034 |
| [11] | J. S. B. Mitchell, Approximation algorithms for geometric separation problems, Tech. Rep., AMS Dept., SUNY Stony Brook, NY (1993). |
| [12] | O’Rourke, J., Aggarwal, A., Maddila, S. and Baldwin, M., An optimal algorithm for finding minimal enclosing triangles, J. Algoritm.7 (1986) 258-269. · Zbl 0606.68038 |
| [13] | C. Seara, On geometric separability, Ph.D. thesis, Polytechnic University of Catalonia (2002). |
| [14] | M. Teichman, Shoving a table into a corner, Tech. Report SOCS-88.11, Computational Geometry Laboratory, McGill University (1988), pp. 99-118. |
| [15] | Welzl, E., Smallest enclosing disks (balls and ellipsoids), Results and New Trends in Computer Science (Springer-Verlag, Austria, 1991), pp. 359-370. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
