Abstract
Let (W,d) be a metric space and S = {s 1 …s k } an ordered list of subsets of W. The distance between p ∈ W and s i ∈ S is d(p, s i ) = min { d(p,q) : q ∈ s i }. S is a resolving set for W if d(x, s i ) = d(y, s i ) for all s i implies x = y. A metric basis is a resolving set of minimal cardinality, named the metric dimension of (W,d). The metric dimension has been extensively studied in the literature when W is a graph and S is a subset of points (classical case) or when S is a partition of W ; the latter is known as the partition dimension problem. We have recently studied the case where W is the discrete space ℤn for a subset of points; in this paper, we tackle the partition dimension problem for classical Minkowski distances as well as polyhedral gauges and chamfer norms in ℤn.
Chapter PDF
Similar content being viewed by others
References
Buczkowski, P., Chartrand, G., Poisson, C., Zhang, P.: On k-dimensional graphs and their bases. Periodica Mathematica Hungarica 46, 9–15 (2003)
Cáceres, J., Hernando, C., Mora, M., Pelayo, I., Puertas, M.: On the metric dimension of infinite graphs. Electronic Notes in Discrete Math. 35, 15–20 (2009)
Chappell, G.G., Gimbel, J.G., Hartman, C.: Bounds on the metric and partition dimensions of a graph. Ars Comb. 88, 349–366 (2008)
Chartrand, G., Eroh, L., Johnson, M., Oellermann, O.: Resolvability in graphs and the metric dimension of a graph. Discrete Applied Math. 105(1-3), 99–113 (2000)
Chartrand, G., Salehi, E., Zhang, P.: On the partition dimension of a graph. Congressus Numerantium 131, 55–66 (1998)
Chartrand, G., Salehi, E., Zhang, P.: The partition dimension of a graph. Aequationes Mathematicae 59, 45–54 (2000)
Harary, F., Melter, R.: On the metric dimension of a graph. Ars Combinatoria 2, 191–195 (1976)
Hardy, G., Wright, E.: An introduction to the theory of numbers, 5th edn. Oxford University Press (October 1978)
Hernando, C., Mora, M., Pelayo, I., Seara, C., Cáceres, J., Puertas, M.: On the metric dimension of some families of graphs. Electronic Notes in Discrete Mathematics 22, 129–133 (2005)
Khuller, S., Raghavachari, B., Rosenfeld, A.: Landmarks in graphs. Discrete Applied Mathematics 70(3), 217–229 (1996)
Melter, R., Tomescu, I.: Metric bases in digital geometry. Computer Vision, Graphics, and Image Processing 25(1), 113–121 (1984)
Rebatel, F., Thiel, É.: Metric Bases for Polyhedral Gauges. In: Debled-Rennesson, I., Domenjoud, E., Kerautret, B., Even, P. (eds.) DGCI 2011. LNCS, vol. 6607, pp. 116–128. Springer, Heidelberg (2011)
Tomescu, I.: Discrepancies between metric dimension and partition dimension of a connected graph. Discrete Mathematics 308(22), 5026–5031 (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rebatel, F., Thiel, É. (2013). On Dimension Partitions in Discrete Metric Spaces. In: Gonzalez-Diaz, R., Jimenez, MJ., Medrano, B. (eds) Discrete Geometry for Computer Imagery. DGCI 2013. Lecture Notes in Computer Science, vol 7749. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-37067-0_2
Download citation
DOI: https://doi.org/10.1007/978-3-642-37067-0_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-37066-3
Online ISBN: 978-3-642-37067-0
eBook Packages: Computer ScienceComputer Science (R0)