×

zbMATH — the first resource for mathematics

On the number of radial orderings of colored planar point sets. (English) Zbl 1374.68661
Márquez, Alberto (ed.) et al., Computational geometry. XIV Spanish meeting on computational geometry, EGC 2011, dedicated to Ferran Hurtado on the occasion of his 60th birthday, Alcalá de Henares, Spain, June 27–30, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-34190-8/pbk). Lecture Notes in Computer Science 7579, 109-118 (2012).
Summary: Let \(n\) be an even natural number and let \(S\) be a set of \(n\) red and \(n\) blue points in general position in the plane. Let \(p \notin S\) be a point such that \(S \cup \{p\}\) is in general position. A radial ordering of \(S\) with respect to \(p\) is a circular ordering of the elements of \(S\) by angle around \(p\). A colored radial ordering is a radial ordering of \(S\) in which only the colors of the points are considered. We show that: the number of distinct radial orderings of \(S\) is at most \(O(n^{4})\) and at least \(\Omega (n^{2})\); the number of colored radial orderings of \(S\) is at most \(O(n^{4})\) and at least \(\Omega (n)\); there exists sets of points with \(\Theta (n^{4})\) colored radial orderings and sets of points with only \(O(n^{2})\) colored radial orderings.
For the entire collection see [Zbl 1253.68016].
MSC:
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bárány, I., Matoušek, J.: Simultaneous partitions of measures by k-fans. Discrete & Comput. Geom. 25, 317–334 (2001) · Zbl 0989.52009 · doi:10.1007/s00454-001-0003-5
[2] Bárány, I., Matoušek, J.: Equipartition of two measures by a 4-fan. Discrete & Comput. Geom. 27, 293–301 (2002) · Zbl 1002.60006 · doi:10.1007/s00454-001-0071-6
[3] Bereg, S.: Equipartitions of measures by 2-fans. Discrete & Comput. Geom. 34, 87–96 (2005) · Zbl 1073.52003 · doi:10.1007/s00454-004-1151-1
[4] Bespamyatnikh, S., Kirkpatrick, D., Snoeyink, J.: Generalizing ham-sandwich cuts to equitable subdivisions. Discrete & Comput. Geom. 24, 605–622 (2000) · Zbl 0966.68156 · doi:10.1007/s4540010065
[5] Deneen, L., Shute, B.: Polygonizations of point sets in the plane. Discrete Comput. Geom. 3(1), 77–87 (1988) · Zbl 0629.52008 · doi:10.1007/BF02187898
[6] Gfeller, B., Mihalák, M., Suri, S., Vicari, E., Widmayer, P.: Counting Targets with Mobile Sensors in an Unknown Environment. In: Kutyłowski, M., Cichoń, J., Kubiak, P. (eds.) ALGOSENSORS 2007. LNCS, vol. 4837, pp. 32–45. Springer, Heidelberg (2008) · Zbl 05253384 · doi:10.1007/978-3-540-77871-4_5
[7] Kannianen, O., Allho, T.M.R.: Minimalist navigation for a mobile robot based on a simple visibility sensor information, pp. 68–75 (2008)
[8] Langerman, S., Steiger, W.: Optimization in Arrangements. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 50–61. Springer, Heidelberg (2003) · Zbl 1036.90512 · doi:10.1007/3-540-36494-3_6
[9] Suri, S., Vicari, E., Widmayer, P.: Simple robots with minimal sensing: From local visibility to global geometry. Int. J. Rob. Res. 27, 1055–1067 (2008) · Zbl 05744886 · doi:10.1177/0278364908095833
[10] Tovar, B., Freda, L., LaValle, S.M.: Using a robot to learn geometric information from permutations of landmarks. In: Topology and Robotics. Contemp. Math., vol. 438, pp. 33–45. Amer. Math. Soc., Providence (2007) · Zbl 1143.68611 · doi:10.1090/conm/438/08443
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.