No Access

ON COMPUTING ENCLOSING ISOSCELES TRIANGLES AND RELATED PROBLEMS

PROSENJIT BOSE

School of Computer Science, Carleton University, 1125 Colonel By Drive, Ottawa, Ontario K1S5B6, Canada

Search for more papers by this author

MERCÈ MORA

Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Jordi Girona 1, Barcelona 08034, Spain

Search for more papers by this author

CARLOS SEARA

Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Jordi Girona 1, Barcelona 08034, Spain

Search for more papers by this author

, and

SAURABH SETHIA

Search for more papers by this author

https://doi.org/10.1142/S0218195911003536Cited by:8 (Source: Crossref)

Abstract

Given a set of n points in the plane, we show how to compute various enclosing isosceles triangles where different parameters such as area or perimeter are optimized. We then study a 3-dimensional version of the problem where we enclose a point set with a cone of fixed apex angle α.

Partially supported by projects MEC MTM2006-01267 and DURSI 2005SGR00692.

Keywords:

References

E. M. Arkinet al., Int. J. Comput. Geom. Appl. 16(1), 1 (2006). Link, Web of Science, Google Scholar
P. K. Agarwal, B. Aronov and M. Sharir, Line traversals of balls and smallest enclosing cylinders in 3 dimensions, 8th ACM-SIAM Symp. Discr. Algorit. pp. 483–492. Google Scholar
A. Aggarwal and J. Park, Notes on searching in multi-dimensional monotone arrays, FOCS pp. 497–512. Google Scholar
B. Bhattacharya and A. Mukhopadhyay, On the minimum perimeter triangle enclosing a convex polygon, JCDCG pp. 84–96. Google Scholar
P. Boseet al., Algorithmica 33, 411 (2002), DOI: 10.1007/s00453-001-0112-9. Crossref, Web of Science, Google Scholar
B. Beckeret al., J. Algorithms 21, 520 (1996), DOI: 10.1006/jagm.1996.0057. Crossref, Web of Science, Google Scholar
T. M. Chan, Int. J. Comput. Geom. Appl. 12, 67 (2002), DOI: 10.1142/S0218195902000748. Link, Web of Science, Google Scholar
J. S. Chang and C. K. Yap, A polynomial solution for potato-peeling and other polygon inclusion and enclosure problems, FOCS pp. 408–416. Google Scholar
B. Chazelleet al., Diameter, width, closest line pair, and parametric searching, 8th Ann. Symp. Comput. Geom. pp. 120–129. Google Scholar
N. De Pano, Polygon approximation with optimized polygonal enclosures: applications and algorithms, PhD Thesis, (1987) . Google Scholar
M. E. Houle and G. T. Toussaint, IEEE Trans. Patt. Anal. Mach. Intell. 10(5), 761 (1988), DOI: 10.1109/34.6790. Crossref, Web of Science, Google Scholar
V. Klee and M. C. Laskowski, J. Algorithms 6, 359 (1985). Crossref, Web of Science, Google Scholar
D. T. Lee and Y. F. Wu, Algorithmica 1, (1986), DOI: 10.1007/BF01840442. Google Scholar
N. Megiddo, Disc. Comput. Geom. 4, 605 (1989), DOI: 10.1007/BF02187750. Crossref, Web of Science, Google Scholar
E. Omaña-Pulido and G. T. Toussaint, J. Mathem. Modell. Algorith. 1, 301 (2002). Crossref, Google Scholar
F. P. Preparata and M. I. Shamos , Computational Geometry, An Introduction ( Springer , 1988 ) . Google Scholar
J. O'Rourkeet al., J. Algorithms 7, (1986). Google Scholar
V. Sacristán, Lower bounds for some geometric problems, Technical Report MA-IR-98-0034, Dpt. de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, 1998 . Google Scholar
E. Schoemeret al., Algorithmica 27(2), 170 (2000). Crossref, Web of Science, Google Scholar
M. Teichmann, Shoving a table into a corner, Snapshots of computational and discrete geometry, Technical Report SOCS-88.11, McGill University (1988), pp. 99–118 . Google Scholar
G. Toussaint, Solving geometric problems with the rotating calipers, Proc. IEEE MELECON'83 p. A10.02/1-4. Google Scholar