×

On optimal disc covers and a new characterization of the Steiner center. (English) Zbl 1341.65009

The authors consider the problem of sphere coverage in a \(d\)-dimensional Euclidean space. In the considered problem they have a set of \(N\) points \(P=\{P_1,P_2,\dots,P_N\}\) in \(\mathbb R^d\) and they take an arbitrary point \(\Omega\in \mathbb R^d\). They define spheres \(S_{P_i}(\Omega)\) as the spheres having the line segments \([\Omega P_i]\) as diameters for \(i=1,2,\dots,N\) and consider the union of the spheres. The authors first prove that the resulting shape of this union covers the convex hull \(CH(P)\) for all \(\Omega\in \mathbb R^d\). Next, they ask a question: What is the location \(\Omega^\ast\) which minimizes the excess volume and hence the total volume of the spheres’ union? The authors give a proof that \(\Omega^\ast\) is the so-called Steiner center of \(CH(P)\), i.e., a weighted centroid of the vertices of a convex polygon, where the weights are proportional to the exterior angles at the vertices. The proof is made only for the case \(d=2\). For \(d>2\), the authors conjecture that a similar results holds.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alt, H.; Aichholzer, O.; Rote, G., Matching shapes with a reference point, (Proc. 10th Ann. Sympos. Comput. Geom. (1994)), 85-92
[2] Berg, C., Abstract Steiner points for convex polytopes, J. London Math. Soc., 4, 1, 176-180 (1971) · Zbl 0222.52006
[3] Carmi, P.; Har-Peled, S.; Katz, M. J., On the Fermat-Weber center of a convex object, Comput. Geom. Theory Appl., 32, 188-195 (2005) · Zbl 1082.65016
[4] Durocher, S.; Kirkpatrick, D., The Steiner center of a set of points: stability, eccentricity, and applications to mobile facility location, Int. J. Comp. Geometry & Applications, 16, 4, 345-371 (2006) · Zbl 1104.65020
[5] Elekes, G., A geometric inequality and the complexity of computing volume, Discrete Comput. Geom., 1, 289-292 (1986) · Zbl 0611.52010
[6] Honsberger, R., Episodes in Nineteenth and Twentieth Century Euclidean Geometry (1995), The Mathematical Association of America · Zbl 0829.01001
[7] Kaiser, M. J.; Morin, T. L., Characterizing centers of convex bodies via optimization, J. Math. Anal. and Applications, 184, 3, 533-559 (1994) · Zbl 0810.52005
[8] Keren, D.; Sharfman, I.; Schuster, A.; Livne, A., Shape sensitive geometric monitoring, IEEE Trans. Knowl. Data Eng., 24, 8, 1520-1535 (2012)
[9] McMullen, P., Valuations and Euler-type relations on certain classes of convex polytopes, Proc. London Math. Soc., 35, 113-135 (1977) · Zbl 0353.52001
[10] Sallee, G. T., A valuation property of Steiner points, Mathematika, 13, 76-82 (1966) · Zbl 0146.44203
[11] Schneider, R., On Steiner points of convex bodies, Israel J. Math., 9, 2, 241-249 (1971) · Zbl 0208.50402
[12] Sharfman, I.; Schuster, A.; Keren, D., A geometric approach to monitoring threshold functions over distributed data streams, (Proc. ACM Int. Conf. Management of Data. Proc. ACM Int. Conf. Management of Data, SIGMOD ’06 (2006)), 301-312
[13] Shephard, G. C., The Steiner point of a convex polytope, Canad. J. Math, 18, 1294-1300 (1966) · Zbl 0145.42801
[14] Shephard, G. C., A uniqueness theorem for the Steiner point of a convex region, J. London Math. Soc., 43, 439-444 (1968) · Zbl 0162.25801
[15] Shephard, G. C., Euler-type relations for convex polytopes, Proc. London Math. Soc., 18, 4, 597-606 (1968) · Zbl 0159.51703
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.