Navigational ambiguity in robot path-finding: Complement metric dimension of symmetric convex planar spaces

1. Introduction

In autonomous robotic systems, navigation through an environment relies heavily on the ability to interpret distances from selected reference points, known as landmarks. These landmarks are modeled mathematically using the framework of graph theory, where the environment is represented as a graph space $X$, and distances are defined through a graph metric. A robot determines its location by comparing distances to the selected landmarks. However, when the chosen set of reference points fails to uniquely distinguish different positions, the robot may encounter navigational ambiguity. Understanding such worst-case scenarios, where the selected landmarks provide insufficient or misleading information, is of critical importance in designing robust localization systems (Khuller et al., 1996; Susilowati et al., 2019).

The graph-theoretic concept of a metric generator serves to model effective landmark placement: it is a subset of vertices such that all other vertices have unique distance representations with respect to it. Conversely, a metric resolving complement consists of a largest set of vertices that, if chosen as landmarks, fail to resolve all positions, thus acting as a source of maximum ambiguity. The cardinality of such a set is called the complement metric dimension, a concept that has applications in both robotic path-finding and intrusion detection in networks.

In this paper, we investigate the complement metric dimension of six families of symmetric convex planar (SCP) spaces, each modeling a structured geometric environment. For each space, we determine the exact value of its complement metric dimension by constructing maximal metric resolving complements and establishing corresponding upper bounds. These results provide insight into the structural limitations of landmark-based navigation in convex environments.

2. Complement Metric Dimension of $D_{\text{n}}$

For $n\ge 3$, the symmetric convex planar (SCP) space $D_n$ consists of four distinct types of points, labeled as $a_i$, $b_i$, $c_i$, and $d_i$ for each $i\in \left[n\right]$, following the structure described in Imran et al. (2012). These vertices are respectively referred to as inner points ($I$), inner-attached points ($IA$), outer-attached points ($OA$), and outer points ($O$). Fig. 1 depicts the general half-structure of $D_n$, highlighting its symmetric and convex configuration.

Close

Fig. 1.

General structural half view of the SCP space $D_n$.

Export to PPT

We begin by presenting two preliminary claims that establish bounds on pairwise distances in metric resolving complements of $D_n$.

Claim 1 If $n\ge 4$ is even, then no pair $(u,v)$ of distinct $I$-, $IA$-, $OA$-, or $O$-points contributes to a metric resolving complement of $D_n$ whenever $m(u,v)<diam\left(D_n\right)-2$.

Proof. It is known from Imran et al. (2012) that a minimum metric generator of $D_n$ consists of three vertices. If all points in such a generator are selected from the same type either all $I$, $IA$, $OA$, or $O$ then their resolving capability is preserved only if the inequality $m\left(x,y\right)\ge diam\left(D_n\right)-2$ holds for every distinct pair $x,y$ in the set.

In order to complete the parity-based analysis, we now present the corresponding situation when $n$ is odd with the proof analogous to Claim 1.

Claim 2 If $n\ge 5$ is odd, then no pair $\left(u,v\right)$ of distinct $I$-, $IA$-, $OA$-, or $O$-points contributes to a metric resolving complement of $D_n$ whenever $m\left(u,v\right)<diam\left(D_n\right)-3$.

Based on these structural bounds, we now determine the exact complement metric dimension of $D_n$.

Theorem 3 For $n\ge 4$, the complement metric dimension of the SCP space $D_n$ is given by:

$\overline{\text{dim}}\left(D_n\right)=\{\begin{array}{cc}2n-4,& \text{if }n \text{is even},\\ 2n-6,& \text{if }n \text{is odd}.\end{array}$

Proof. We divide the proof into two cases based on the parity of $n$.

Case I: $n$ is even. Define a set

$S=\{a_i,b_j,c_k,d_l;1\le i\le \frac{n}{2},3\le j\le \frac{n}{2},\frac{n}{2}\le k\le n-3,\frac{n}{2}\le l<n\}$

containing $2n-4$ vertices. Then the pair $\left(b_n,c_n\right)$ in $V\left(D_n\right)\backslash S$ satisfies $c_S\left(b_n\right)=c_S\left(c_n\right)$, so $S$ is a metric resolving complement. Thus, $\overline{\text{dim}}\left(D_n\right)\ge 2n-4$.

Assume, for contradiction, that a resolving complement $S\text{'}$ exists with $\left(S\text{'}\right)>2n-4$, say $\left(S\text{'}\right)=2n-3$. Then there must be a pair of points in $S\text{'}$ from the same point-type with distance less than $diam\left(D_n\right)-2$, contradicting Claim 1. Hence, $\overline{\text{dim}}\left(D_n\right)\le 2n-4$.

Having completed the analysis for even $n$, we now examine the complementary case when $n$ is odd.

Case II: $n$ is odd. Define a set

$S=\left(\begin{array}{c}{a}_i,b_j,c_k,d_l;1\le i\le \frac{n-1}{2},3\le j\le \frac{n-1}{2},\\ \frac{n-1}{2}<k\le n-3,\frac{n}{2}\le l<n\end{array}\right)$

containing $2n-6$ vertices. Then the pair $\left(b_n,c_n\right)$ in $V\left(D_n\right)\backslash S$ satisfies $c_S\left(b_n\right)=c_S\left(c_n\right)$, so $S$ is a metric resolving complement. Thus, $\overline{\text{dim}}\left(D_n\right)\ge 2n-6$.

Assume, for contradiction, that a resolving complement $S\text{'}$ exists with $\left(S\text{'}\right)>2n-6$, say $\left(S\text{'}\right)=2n-5$. Then a pair of points in $S\text{'}$ must exist from the same point-type with distance less than $diam\left(D_n\right)-3$, contradicting Claim 2. Therefore, $\overline{\text{dim}}\left(D_n\right)\le 2n-6$.

3. Complement Metric Dimension of ${\text{R}}_{\text{n}}$

For $n\ge 3$, the SCP space $R_n$ consists of three distinct types of points labeled as $a_i$, $b_i$, and $c_i$ for $i\in \left(n\right)$, as described in (Imran et al., 2012). These points correspond to inner points ($I$), middle points ($M$), and outer points ($O$) respectively. The structural pattern of $R_n$ is shown in Fig. 2.

Close

Fig. 2.

General structural half view of the SCP space $R_n.$

Export to PPT

To determine the complement metric dimension of $R_n$, we first present two preparatory claims about intra-type distances.

Claim 4 If $n\ge 6$ is even, then no pair $\left(u,v\right)$ of distinct $I$-, $M$-, or $O$-points contributes to a metric resolving complement of $R_n$ whenever $m\left(u,v\right)<diam\left(R_n\right)-1$.

Proof. According to Imran et al. (2012), the minimum metric generator of $R_n$ consists of three vertices. When the metric generator includes vertices of only one type either all $I$, $M$, or $O$ then it can distinguish all other points only if the pairwise distances satisfy $m\left(x,y\right)\ge diam\left(R_n\right)-1$ for all distinct $x,y\in S$.

A parallel restriction appears in the odd case of $n$, as described next.

Claim 5 If $n\ge 5$ is odd, then no pair $\left(u,v\right)$ of distinct $I$-, $M$-, or $O$-points contributes to a metric resolving complement of $R_n$ whenever $m\left(u,v\right)<diam\left(R_n\right)-2$.

We now derive the exact expression for the complement metric dimension of $R_n$.

Theorem 6 For $n\ge 5$, the complement metric dimension of the SCP space $R_n$ is given by:

$\overline{\text{dim}}\left(R_n\right)=\{\begin{array}{cc}\frac{3n}{2},& \text{if }n \text{is even},\\ n-1,& \text{if }n \text{is odd}.\end{array}$

Proof. We analyze both cases based on the parity of $n$.

Case I: $n$ is even. Consider the set

$S=\{a_i,b_j,c_k;1\le i\le \frac{n}{2},\frac{n}{2}<j,k\le n\}$

which contains $\frac{3n}{2}$ points. The vertices $a_{n/2+1}$ and $b_{n/2}$ in $V\left(R_n\right)\backslash S$ satisfy $c_S\left(a_{n/2+1}\right)=c_S\left(b_{n/2}\right)$, making $S$ a resolving complement. Therefore, $\overline{\text{dim}}\left(R_n\right)\ge \frac{3n}{2}$.

Assume, for contradiction, that a complement exists with more than $\frac{3n}{2}$ points. Let $\left(S\text{'}\right)=\frac{3n}{2}+1$. Then some pair within the same type must violate Claim 1, i.e., $m\left(u,v\right)<diam\left(R_n\right)-1$, contradicting the resolving condition. Thus, $\overline{\text{dim}}\left(R_n\right)\le \frac{3n}{2}$.

To complete the proof, we now consider the remaining case corresponding to odd $n$.

Case II: $n$ is odd. Let

$S=\{a_i,b_j,c_k;1\le i\le \frac{n-1}{2},\frac{n-1}{2}<j,k\le n-1\}$

be a set of $n-1$ points. The vertices $a_{\left(n+1\right)/2}$ and $b_{\left(n-1\right)/2}$ in $V\left(R_n\right)\backslash S$ satisfy $c_S\left(a_{\left(n+1\right)/2}\right)=c_S\left(b_{\left(n-1\right)/2}\right)$, hence $S$ is a metric resolving complement. So, $\overline{\text{dim}}\left(R_n\right)\ge n-1$.

Assume a complement $S\text{'}$ exists with size $n$. Then some pair within $S\text{'}$ must violate Claim 2, i.e., $m\left(u,v\right)<diam\left(R_n\right)-2$, contradicting the resolving condition. Therefore, $\overline{\text{dim}}\left(R_n\right)\le n-1$.

4. Complement Metric Dimension of ${\text{Q}}_{\text{n}}$

For $n\ge 3$, the SCP space $Q_n$ is composed of four distinct types of points, labeled $a_i$, $b_i$, $c_i$, and $d_i$ for each $i\in \left[n\right]$, as introduced in Imran et al. (2012). These points are categorized as inner points ($I$), middle points ($M$), interior points ($INT$), and outer points ($O$), respectively. The half-structure of $Q_n$ is illustrated in Fig. 3.

Close

Fig. 3.

General structural half view of the SCP space $Q_n$.

Export to PPT

We begin by stating two conditional claims related to intra-type distances in resolving complements.

Claim 7 If $n\ge 6$ is even, then no pair $\left(u,v\right)$ of distinct $I$-, $M$-, $INT$-, or $O$-points contributes to a metric resolving complement of $Q_n$ whenever $m\left(u,v\right)<diam\left(Q_n\right)-2$.

Proof. As established in Imran et al. (2012), three vertices suffice to form a minimum metric generator of $Q_n$. If all selected vertices belong to the same type, they can resolve the space only if the condition $m\left(x,y\right)\ge diam\left(Q_n\right)-2$ holds for every pair of distinct vertices in the set.

An additional refinement is required when $n$ is odd, as stated in the following claim with the proof similar to the Claim 7.

Claim 8 If $n\ge 7$ is odd, then

• 1.

  No pair of distinct $I$-, $M$-, or $O$-points contributes to a metric resolving complement of $Q_n$ whenever $m\left(u,v\right)<diam\left(Q_n\right)-3$.

• 2.

  No pair of distinct $INT$-points contributes whenever $m\left(u,v\right)<diam\left(Q_n\right)-2$.

Now, we present the exact complement metric dimension of $Q_n$.

Theorem 9 For $n\ge 6$, the complement metric dimension of the SCP space $Q_n$ is given by:

$\overline{\text{dim}}\left(Q_n\right)=\left(\begin{array}{cc}2n-1,& \text{if }n \text{is even},\\ 2n-2,& \text{if }n \text{is odd}.\end{array}\right)$

Proof. We examine both cases according to the parity of $n$.

Case I: $n$ is even. Define the set

$S=\left(a_i,b_j,c_k,d_l;1\le i,j\le \frac{n}{2},2\le k\le \frac{n}{2},\frac{n}{2}<l\le n\right)$

which contains $2n-1$ vertices. The pair $\left(b_n,c_1\right)$ in $V\left(Q_n\right)\backslash S$ satisfies $c_S\left(b_n\right)=c_S\left(c_1\right)$, implying that $S$ is a resolving complement. Therefore, $\overline{\text{dim}}\left(Q_n\right)\ge 2n-1$.

Assume a larger complement of size $2n$ exists. Then at least one pair of same-type points in $S$ must satisfy $m\left(u,v\right)<diam\left(Q_n\right)-2$, violating Claim 1. Hence, $\overline{\text{dim}}\left(Q_n\right)\le 2n-1$.

We now turn to the second case, which arises when $n$ is an odd integer.

Case II: $n$ is odd. Let

$S=\{a_i,b_j,c_k,d_l;1\le i,j\le \frac{n-1}{2},2\le k\le \frac{n+1}{2},\frac{n+1}{2}<l\le n\}$

with $\left(S\right)=2n-2$. Again, $\left(b_n,c_1\right)$ belong to $V\left(Q_n\right)\backslash S$ and have identical codes, confirming that $S$ is a resolving complement. So $\overline{\text{dim}}\left(Q_n\right)\ge 2n-2$.

Assume $\left(S\text{'}\right)=2n-1$. Then either:

a pair of $I$-, $M$-, or $O$-points satisfies $m\left(u,v\right)<diam\left(Q_n\right)-3$, or

a pair of $INT$-points satisfies $m\left(u,v\right)<diam\left(Q_n\right)-2$,

contradicting Claim 2. Therefore, $\overline{\text{dim}}\left(Q_n\right)\le 2n-2$.

5. Complement Metric Dimension of ${\text{S}}_{\text{n}}$

For $n\ge 3$, the SCP space $S_n$ comprises four types of points, denoted as $a_i$, $b_i$, $c_i$, and $d_i$ for $i\in \left(n\right)$, as discussed in Imran et al. (2010). These represent inner points ($I$), interior points ($INT$), exterior points ($EXT$), and outer points ($O$) respectively. The structural arrangement is illustrated in Fig. 4.

Close

Fig. 4.

General structural half view of the SCP space $S_n$.

Export to PPT

We begin by establishing two key claims that restrict the behavior of intra-type vertex pairs in resolving complements.

Claim 10 If $n\ge 6$ is even, then no pair $\left(u,v\right)$ of distinct $I$-, $INT$-, $EXT$-, or $O$-points contributes to a metric resolving complement of $S_n$ whenever $m\left(u,v\right)<diam\left(S_n\right)-2$.

Proof. According to Imran et al. (2010), three vertices suffice to generate a minimum metric basis of $S_n$. When such a basis consists solely of vertices from a single type, the condition $m\left(x,y\right)\ge diam\left(S_n\right)-2$ must hold for all distinct $x,y$ in the set for it to function as a valid generator.

The odd-valued case of $n$ follows a similar pattern, as detailed in the next claim.

Claim 11 If $n\ge 7$ is odd, then no pair $\left(u,v\right)$ of distinct $I$-, $INT$-, $EXT$-, or $O$-points contributes to a metric resolving complement of $S_n$ whenever $m\left(u,v\right)<diam\left(S_n\right)-3$.

We now state and prove the main result for this section.

Theorem 12 For $n\ge 6$, the complement metric dimension of the SCP space $S_n$ is given by:

$\overline{\text{dim}}\left(S_n\right)=\left(\begin{array}{cc}2n,& \text{if }n \text{is even},\\ 2n-2,& \text{if }n \text{is odd}.\end{array}\right)$

Proof. We examine the two cases based on the parity of $n$.

Case I: $n$ is even. Define the set

$S=\{a_i,b_j,c_k,d_l;1\le i\le \frac{n}{2},\frac{n}{2}<j,k,l\le n\}$

which contains $2n$ vertices. The pair $\left(a_{n/2+1},b_{n/2}\right)$ in $V\left(S_n\right)\backslash S$ satisfies $c_S\left(a_{n/2+1}\right)=c_S\left(b_{n/2}\right)$, showing that $S$ is a metric resolving complement. Thus, $\overline{\text{dim}}\left(S_n\right)\ge 2n$.

Suppose a larger resolving complement $S\text{'}$ exists with $\left(S\text{'}\right)=2n+1$. Then some pair within $S\text{'}$ of the same type must violate Claim 1, i.e., $m\left(x,y\right)<diam\left(S_n\right)-2$. This contradiction implies $\overline{\text{dim}}\left(S_n\right)\le 2n$.

For completeness, we next analyze the odd-valued case of $n$.

Case II: $n$ is odd. Let

$S=\{a_i,b_j,c_k,d_l;1\le i\le \frac{n-1}{2},\frac{n-1}{2}<j,k,l\le n-1\}$

with $\left(S\right)=2n-2$. The pair $\left(a_{\left(n+1\right)/2},b_{\left(n-1\right)/2}\right)$ in $V\left(S_n\right)\backslash S$ satisfies $c_S\left(a_{\left(n+1\right)/2}\right)=c_S\left(b_{\left(n-1\right)/2}\right)$, confirming $S$ as a metric resolving complement. Hence, $\overline{\text{dim}}\left(S_n\right)\ge 2n-2$.

Assume $\left(S\text{'}\right)=2n-1$. Then there exists a pair $\left(x,y\right)$ in $S\text{'}$ of the same type such that $m\left(x,y\right)<diam\left(S_n\right)-3$, violating Claim 2. Thus, $\overline{\text{dim}}\left(S_n\right)\le 2n-2$.

6. Complement Metric Dimension of ${\text{T}}_{\text{n}}$

For $n\ge 3$, the SCP space $T_n$ consists of four distinct types of points, denoted by $a_i$, $b_i$, $c_i$, and $d_i$ for each $i\in \left(n\right)$, as discussed in Imran et al. (2010). These are referred to as inner points ($I$), interior points ($INT$), exterior points ($EXT$), and outer points ($O$). Fig. 5 illustrates the half-structure of $T_n$, revealing its symmetric and layered design.

Close

Fig. 5.

General structural half view of the SCP space $T_n$.

Export to PPT

We begin with two structural claims that guide the determination of the complement metric dimension.

Claim 13 If $n\ge 6$ is even, then

• 1.

  No pair of distinct $I$-, $INT$-, or $EXT$-points contributes to a resolving complement of $T_n$ whenever $m\left(u,v\right)<diam\left(T_n\right)-2$,

• 2.

  No pair of distinct $O$-points contributes whenever $m\left(u,v\right)<diam\left(T_n\right)-3$.

Proof. It is known from Imran et al. (2010) that three vertices form a minimum metric generator of $T_n$. If the generator contains vertices of the same type, its resolving property holds only when the stated bounds on distances are respected.

A comparable restriction holds when $n$ is odd, as described in the subsequent claim.

Claim 14 If $n\ge 7$ is odd, then no pair of distinct $I$-, $INT$-, $EXT$-, or $O$-points contributes to a metric resolving complement of $T_n$ whenever $m\left(u,v\right)<diam\left(T_n\right)-2$.

We now determine the complement metric dimension of $T_n$.

Theorem 15 For $n\ge 6$, the complement metric dimension of the SCP space $T_n$ is given by:

$\overline{\text{dim}}\left(T_n\right)=\{\begin{array}{cc}2n-1,& \text{if }n \text{is even},\\ 2n-2,& \text{if }n \text{is odd}.\end{array}$

Proof. We proceed by parity-based case analysis.

Case I: $n$ is even. Define the set

$S=\left(a_i,b_j,c_k,d_l;1\le i\le \frac{n}{2},\frac{n}{2}\le j,k\le n-1,\frac{n}{2}\le l\le n-1\right)$

with cardinality $2n-1$. The pair $\left(a_n,b_n\right)$ in $V\left(T_n\right)\backslash S$ satisfies $c_S\left(a_n\right)=c_S\left(b_n\right)$, verifying that $S$ is a resolving complement. Thus, $\overline{\text{dim}}\left(T_n\right)\ge 2n-1$.

Assume $\left(S\text{'}\right)=2n$. Then some pair of same-type points must violate Claim 1 either with $m\left(x,y\right)<diam\left(T_n\right)-2$ for non-$O$ types, or $m\left(x,y\right)<diam\left(T_n\right)-3$ for $O$-points. This contradiction implies $\overline{\text{dim}}\left(T_n\right)\le 2n-1$.

We now analyze the second scenario, namely when $n$ takes an odd value.

Case II: $n$ is odd. Let

$S=\{a_i,b_j,c_k,d_l;1\le i\le \frac{n-1}{2},\frac{n-1}{2}<j,k\le n-1,\frac{n-1}{2}<l<n-1\}$

with $\left(S\right)=2n-2$. The pair $\left(a_n,b_n\right)$ satisfies $c_S\left(a_n\right)=c_S\left(b_n\right)$, establishing that $S$ is a resolving complement. So, $\overline{\text{dim}}\left(T_n\right)\ge 2n-2$.

Assume $\left(S\text{'}\right)=2n-1$. Then some pair in $S\text{'}$ violates Claim 2 by having a distance less than $diam\left(T_n\right)-2$, contradicting the resolving condition. Hence, $\overline{\text{dim}}\left(T_n\right)\le 2n-2$.

7. Complement Metric Dimension of ${\text{U}}_{\text{n}}$

For $n\ge 3$, the SCP space $U_n$ comprises five distinct types of points, labeled $a_i$, $b_i$, $c_i$, $d_i$, and $e_i$ for each $i\in \left(n\right)$, as studied in Imran et al. (2010). These correspond to inner points ($I$), interior points ($INT$), two layers of exterior points ($EXT$), and outer points ($O$), respectively. The half-structure of $U_n$ is illustrated in Fig. 6.

Close

Fig. 6.

General structural half view of the SCP space $U_n$.

Export to PPT

The following claims provide bounds on distances among intra-type pairs in resolving complements.

Claim 16 If $n\ge 6$ is even, then no pair $\left(u,v\right)$ of distinct $I$-, $INT$-, $EXT$-, or $O$-points contributes to a resolving complement of $U_n$ whenever $m\left(u,v\right)<diam\left(U_n\right)-3$.

Proof. As shown in Imran et al. (2010), three vertices form a minimum resolving set for $U_n$. If all selected points are of the same type, their distinguishing power is preserved only if their pairwise distances meet or exceed $diam\left(U_n\right)-3$.

The corresponding condition for odd values of $n$ is stated in the next claim.

Claim 17 If $n\ge 7$ is odd, then no pair $\left(u,v\right)$ of distinct $I$-, $INT$-, $EXT$-, or $O$-points contributes to a metric resolving complement of $U_n$ whenever $m\left(u,v\right)<diam\left(U_n\right)-4$.

We now state and prove the final main result.

Theorem 18 For $n\ge 6$, the complement metric dimension of the SCP space $U_n$ is given by:

$\overline{\text{dim}}\left(U_n\right)=\left(\begin{array}{cc}\frac{5n-8}{2},& \text{if }n \text{is even},\\ \frac{5n-13}{2},& \text{if }n \text{is odd}.\end{array}\right)$

Proof. We consider both parity cases for $n$.

Case I: $n$ is even. Define the set

$S=\left(\begin{array}{c}{a}_i,b_j,c_k,d_l,e_m;1\le i,j\le \frac{n}{2},3\le k\le \frac{n}{2},\\ \frac{n}{2}<l\le n-3,\frac{n}{2}<m<n\end{array}\right)$

with $\left(S\right)=\frac{5n-8}{2}$. The pair $\left(c_n,d_n\right)$ in $V\left(U_n\right)\backslash S$ satisfies $c_S\left(c_n\right)=c_S\left(d_n\right)$, showing that $S$ is a resolving complement. Hence, $\overline{\text{dim}}\left(U_n\right)\ge \frac{5n-8}{2}$.

Suppose a larger resolving complement $S\text{'}$ exists with $\left(S\text{'}\right)=\frac{5n-8}{2}+1$. Then a pair of same-type points in $S\text{'}$ must violate Claim 1 by having a distance less than $diam\left(U_n\right)-3$, contradicting the resolving property. Thus, $\overline{\text{dim}}\left(U_n\right)\le \frac{5n-8}{2}$.

Having resolved the even case, we proceed to investigate the odd case of $n$.

Case II: $n$ is odd. Let

$S=\left(\begin{array}{c}{a}_i,b_j,c_k,d_l,e_m;1\le i,j\le \frac{n-1}{2},3\le k\le \frac{n-1}{2},\\ \frac{n-1}{2}<l\le n-3,\frac{n-1}{2}<m<n\end{array}\right)$

with $\left(S\right)=\frac{5n-13}{2}$. The pair $\left(c_n,d_n\right)$ in $V\left(U_n\right)\backslash S$ satisfies $c_S\left(c_n\right)=c_S\left(d_n\right)$, proving that $S$ is a resolving complement. Therefore, $\overline{\text{dim}}\left(U_n\right)\ge \frac{5n-13}{2}$.

Assume a complement $S\text{'}$ of size $\frac{5n-13}{2}+1$ exists. Then some same-type pair in $S\text{'}$ must satisfy $m\left(u,v\right)<diam\left(U_n\right)-4$, violating Claim 2. Hence, $\overline{\text{dim}}\left(U_n\right)\le \frac{5n-13}{2}$.

Table 1 summarizes the final results obtained from each SCP space analyzed:

8. Concluding Remarks and Summary

This study explored the structural limitations in landmark-based navigation through the lens of complement metric dimension (CMD) in six symmetric convex planar (SCP) spaces. Each SCP space was analyzed to determine the maximum cardinality of a metric resolving complement a set of points that fails to distinguish all other points based on metric codes.

These complements model the concept of navigational ambiguity in robot pathfinding. Unlike traditional metric generators which aid in unique identification, resolving complements represent configurations that cause maximum confusion in spatial navigation. By characterizing these worst-case sets, our work contributes to understanding robustness limits in graph-based localization systems.

The exact values of the complement metric dimensions were derived through constructive combinatorial arguments and upper-bounding claims based on structural diameter restrictions. Table 1 summarizes the final results obtained for each SCP space analyzed:

Due to the symmetric and layered nature of these SCP spaces, we observe a consistent trend: the complement metric dimension tends to exceed half of the total number of vertices (order) in the graph. This structural insight motivates the following conjecture for future investigation.

Conjecture: The complement metric dimension of any SCP space $X$ with order $\left(V\left(X\right)\right)\ge 3$ satisfies

$\overline{\text{dim}}\left(X\right)>\lfloor \left(V\left(X\right)\right)/2\rfloor .$

This work lays the groundwork for further explorations into generalized classes of convex polytopes, higher-dimensional grid spaces, and applications in uncertainty modeling for robotics, sensor networks, and chemical graph theory.