# Effects of electrons on nuclear clock transition frequency in 229Th ions

V. A. Dzuba and V. V. Flambaum  School of Physics, University of New South
Wales, Sydney 2052, Australia

###### Abstract

We perform calculations of the energy shift of the nuclear clock transition
frequency 229Th as a function of the number of electrons in Th ion. We
demonstrate that the dependence of the nuclear frequency on electron
configuration is significant. E.g., removing one electron from the atom leads
to relative shift of the nuclear frequency $\sim 10^{-7}$, which is twelve
orders of magnitude larger than expected relative uncertainty of the nuclear
clock transition frequency ($\sim 10^{-19}$). This leads to difference of the
nuclear clock frequencies in Th IV, Th III, Th II and Th I. The relative
change of the nuclear frequency between neutral Th and its bare nucleus is 1%.
We also calculate the field shift constants for isotopic and isomeric shifts
of atomic electron transitions in Th ions.

Nucleus of the 229Th isotope has a unique feature of having very low-energy
excitation connected to the ground state by the magnetic dipole (M1)
transition (see, e.g. Reviews Rev ; Rev1  and references therein). The latest,
most precise measurements, give the value of 8.338(24) eV wn  (see also wn1 ;
wn2 ; wn3 ; wn4 ; wn5 ) for the energy of this excitation, which is very small
on nuclear scale. This feature attracted many researches for plans to build
nuclear clock of exceptionally high accuracy - see e.g. PeikTamm ; Thm . The
projected relative uncertainty is expected to reach $10^{-19}$ Th3+ . In
addition, there are strong arguments that this nuclear clock would be very
sensitive to physics beyond standard model including space-time variation of
the fundamental constants, violation of the Lorentz invariance and Einstein
equivalence principle, and search for scalar and axion dark matter fields vara
; Lorentz ; varq ; vara1 ; vara2 ; vara3 ; vara4 ; Arvanitaki ; Stadnik .
There are plans to use Th ions of different ionisation degree Th3+ ; Th+ ; dr
and even solid-state Th nuclear clock Hudson ; ThSS ; ThSS1 . In this work we
show that in all these systems the frequency of the nuclear clock will be
different. This is due to the Coulomb interaction of atomic electrons with the
nucleus, leading to the significant electronic shift of the nuclear transition
frequency. There is also a smaller shift due to the magnetic interaction.

This electronic shift depends on electron configuration and it is different in
different systems, like Th IV, Th III, Th II and Th I , leading to different
nuclear frequencies. This shift for electronic state $a$ is given by

$\Delta E_{a}=F_{a}\delta\langle r^{2}\rangle,$ (1)

where $F_{a}$ is the field shift constant of state $a$ which can be obtained
from atomic calculations; $\delta\langle r^{2}\rangle$ is the change of the
nuclear root-mean square radius between the excited and ground nuclear states.
The most accurate value for $\delta\langle r^{2}\rangle$ was recently derived
in Ref. dr , ${}^{229m,229}\delta\langle r^{2}\rangle=0.0105(13)~{}{\rm
fm}^{2}$. This enables us to determine the electronic shift of nuclear
transition frequency for different thorium systems by calculating the field
shift constants $F_{a}$ and using (1). For example, difference of the nuclear
frequencies between Th III and Th IV is given by

$\Delta\omega_{N}=(F_{a}(\text{Th~{}III})-F_{a}(\text{Th~{}IV}))\delta\langle
r^{2}\rangle,$ (2)

State $a$ in this case is the ground electronic state of the ion.

Note that these field shift constants $F$ appear also in the calculations of
the isotopic and isomeric field shifts of electronic transition frequencies.
The difference is that in the isotopic and isomeric shifts we need difference
of $F$ for final state $b$ and initial state $a$ of the electronic transition.
The nuclear state does not change in this electronic transition. For isotope
shift it is usually the ground nuclear state. For isomeric shift it is
isomeric (excited) state or ground state of the same nucleus. The isotopic and
isomeric field shifts of the electronic transition frequency are given by

$\Delta\omega_{ab}=(F_{b}-F_{a})\delta\langle r^{2}\rangle,$ (3)

Numerical values of $\Delta\omega_{N}$ and $\Delta\omega_{ab}$ can be
calculated using values of the constants $F$ for different electron states in
Th IV, Th III, Th II and Th I presented in the Table 1 . Note that we do not
include a contribution of core electrons which cancels out in the difference
of the values of $F$. For the isomeric shifts one may use
${}^{229m,229}\delta\langle r^{2}\rangle=0.0105(13)~{}{\rm fm}^{2}$ measured
in Ref. dr .

We use the combination of the single-double coupled cluster and the
configuration interaction methods (SD+CI, SD+CI ) and random-phase
approximation (RPA) method to perform the calculations. The SD+CI method gives
us the wave functions, while the RPA method gives an effective operator of the
field shift. Corresponding equations have a form (see e.g. TDHF )

$(\hat{H}^{\rm HF}-\epsilon_{c})\delta\psi_{c}=-(\hat{F}+\delta V_{\rm
core}),$ (4)

where $H^{\rm HF}$ is the relativistic Hartree-Fock operator for the atomic
core, index $c$ numerates single-electron states in the core, $\psi_{c}$ and
$\delta\psi_{c}$ are corresponding single-electron functions and corrections
due to the field shift operator $\hat{F}$, and $\delta V_{\rm core}$ is the
change of the self-consistent Hartree-Fock potential due to the change in all
core functions. Solving Eqs. (4) self-consistently allows to determine $\delta
V_{\rm core}$. Note that the core is the same for Th IV, Th III, Th II and Th
I. Therefore the SD+CI and RPA equations need to be solved only once. Then the
field shift constant is given by

$F_{a}=\langle a|\hat{F}+\delta V_{\rm core}|a\rangle.$ (5)

We use hat to distinguish between the field shift constant $F$ and the field
shift operator $\hat{F}=\delta V_{\rm nuc}/\delta\langle r^{2}\rangle$. The
wave function $|a\rangle$ in (5) is the many-electron wave function for
valence electrons found in the SD+CI calculations. It has one, two, three or
four valence electrons.

The results of the calculations are presented in Table 1. We present energy
levels and field shift constants for the ground and some excited states of Th
IV, Th III, Th II, and Th I. We have chosen low-energy excited states and also
some other states of Th III and Th I for which other calculations and
experimental data on isotope shift are available dr . The values of the field
shift constants are compared with earlier calculations in Ref. dr .

The difference of the field shift constants between our calculations and
calculations in Ref. dr  is few per cent. This difference may be used as an
accuracy estimate since the calculations have been done by different methods.
The largest difference is for the ground state of Th II, which is 10%.
However, our number leads to more consistent results for values of
$\delta\langle r^{2}\rangle$ extracted from the isotope shift measurements in
ions Th II and Th III. Indeed, using our numbers, $F$=49.6 GHz/fm2 for the
ground state and $F$=-29.1 GHz/fm2 for the state at $E$=17122 cm-1, for
extracting the difference in root-mean-square radii $\delta\langle
r^{2}\rangle^{232,229}$ from the isotope shift data dr  leads to the value
$\delta\langle r^{2}\rangle^{232,229}$ = 0.321(32) fm2 (we assume 10%
uncertainty for the values of $F$), which is closer to the data extracted from
four transitions in Th III (0.315(32), 0.312(42), 0.338(44), 0.322(53), see
Table I in dr ). When all five numbers are taken into account, four numbers
for Th III from Ref. dr  and our number for Th II, 0.321(32), the final result
is $\delta\langle r^{2}\rangle^{232,229}$ = 0.320(15) fm2 (the final value of
dr  is $\delta\langle r^{2}\rangle^{232,229}$ = 0.299(15) fm2). Our result is
in better agreement with the latest most accurate literature value
$\delta\langle r^{2}\rangle^{232,229}$=0.334(8) fm2 presented in Ref. Marinova
. The new value of $\delta\langle r^{2}\rangle^{232,229}$ leads to slightly
different value of $\delta\langle r^{2}\rangle^{229m,229}$. Using the ratio of
the isomeric and isotopic shifts from Ref. Thm  we get $\delta\langle
r^{2}\rangle^{229m,229}$ = 0.0112(13) fm2. It is 7% larger but agrees within
error bars wth the value $\delta\langle r^{2}\rangle^{229m,229}$ = 0.0105(13)
fm2 presented in dr . We are going to use our new number in further analysis.

It is instructive to explain why the field shift constants $F$ have different
signs for different electron states. Orbitals $s_{1/2}$ and $p_{1/2}$
penetrate nucleus and are highly sensitive to the nuclear radius (remind the
reader that the lower component of the Dirac spinor of the relativistic
$p_{1/2}$ orbital has angular quantum numbers of $s_{1/2}$ orbital). An
increase of the nuclear radius leads to decrease of the attraction to the
nucleus, therefore energies $s_{1/2}$ and $p_{1/2}$ move up and constant $F$
is positive. Higher orbitals $p_{3/2}$, $d$ and $f$ do not penetrate nucleus,
so the direct term $\hat{F}$ in Eq. (5) is negligible. The effect comes from
the correction to the electron core potential $\delta V_{\rm core}$ which is
dominated by the Coulomb field of $s_{1/2}$ electrons. Increase of the nuclear
radius makes attraction to the nucleus weaker, increases the radii of the
$s_{1/2}$ orbitals and makes negative correction $\delta V_{\rm core}$ to the
core electron Coulomb potential. This is why $F$ for $p_{3/2}$, $d$ and $f$
electrons is negative. We may also explain this sign from another end. Adding
valence $p_{3/2}$, $d$ or $f$ electron increases positive Coulomb energy of
the electron repulsion. As a result, the $s_{1/2}$ electron energies and
distances from the nucleus increase and their sensitivity to the change of the
nuclear radius decreases. Thus, the effect of the higher wave valence electron
is negative.

Table 1: Field shift constant $F$ for the ground and some excited states of Th IV, Th III, Th II, and Th I. Atom | State | Expt. energy |  $F$ (GHz/fm2)
---|---|---|---
or ion |  |  | (cm-1) Th-exp  | Present | Ref.dr
Th IV | $5f$ |  2F${}^{o}_{5/2}$ | 0 | -55.0 |
| $5f$ |  2F${}^{o}_{7/2}$ | 4325 | -53.0 |
| $6d$ |  2D3/2 | 9193 | -23.3 |
| $6d$ |  2D5/2 | 14586 | -20.5 |
| $7s$ |  2S1/2 | 23130 | 92.1 |
| $7p$ |  2P${}^{o}_{1/2}$ | 60239 | 2.7 |
| $7p$ |  2P${}^{o}_{3/2}$ | 73055 | -5.3 |
Th III | $5f6d$ |  3H${}^{o}_{4}$ | 0 | -68.0 | -68.7
| $6d^{2}$ |  3F2 | 63 | -39.9 | -36.6
| $5f^{2}$ |  3H4 | 15148 | -83.3 | -89.5
| $5f6d$ |  1P${}^{o}_{1}$ | 20711 | -62.2 | -63.6
| $5f^{2}$ |  3F4 | 21784 | -86.5 | -85.5
| $5f^{2}$ |  3P0 | 29300 | -82.2 | -84.1
Th II | $6d^{2}7s$ |  2D3/2 | 0 | 49.6 | 54.6
| $5f6d^{2}$ | $*_{3/2}$ |  | -65.0 |
| $5f6d7s$ | $*_{3/2}$ | 15145 | -45.8 |
| $5f6d7s$ | $*_{3/2}$ | 15711 | -36.9 |
| $5f6d^{2}$ | $*_{3/2}$ | 17122 | -29.1 | -31.6
| $5f6d7s$ |  2F${}^{o}_{5/2}$ | 12472 | -18.3 |
| $5f6d7s$ | $*_{5/2}$ |  | -36.3 |
| $5f6d7s$ |  4D${}^{o}_{5/2}$ | 14545 | -63.9 |
| $5f6d7s$ | $*_{5/2}$ | 16033 | -46.8 |
Th I | $6d^{2}7s^{2}$ |  3F2 | 0 | 58.6 |

Using the field shift constants for the ground states of each ion from Table 1
(we use our numbers for consistency), the value $\delta\langle
r^{2}\rangle^{229m,229}=0.0112(13)~{}{\rm fm}^{2}$ (see above) and formula
similar to (2) we obtain the differences between nuclear frequencies in
different thorium ions. The results are presented in Table 2. We see that the
difference is huge. It exceeds the projected relative uncertainty of the
nuclear clocks by many orders of magnitude. It is worth noting that the shift
does not contribute to the uncertainty budget. It only means that the
frequency of the nuclear transition is different in different thorium systems.

Table 2: Change of nuclear frequency $\omega_{N}$ between ions of 229Th. Ions | $\Delta\omega_{N}$ | $\Delta\omega_{N}/\omega_{N}$
---|---|---
|  |  | (GHz) | (eV) |
Th I | $-$ | Th II | 0.10 | $4.3\times 10^{-7}$ | $5.0\times 10^{-8}$
Th II | $-$ | Th III | 1.3 | $5.6\times 10^{-6}$ | $6.4\times 10^{-7}$
Th III | $-$ | Th IV | -0.15 | $-6.5\times 10^{-7}$ | $-7.3\times 10^{-8}$
Th II | $-$ | Th IV | 1.2 | $5.2\times 10^{-6}$ | $5.9\times 10^{-7}$

It is interesting to determine the nuclear frequency difference between
neutral (or nearly neutral) 229Th and bare 229Th nucleus. This difference is
strongly dominated by contributions from $1s$ electrons. Using the RPA
calculation (4) we get $F(1s)=8.23\times 10^{8}$ MHz/fm2. The total energy
shift caused be two $1s$ electrons is $1.73\times 10^{7}$ MHz; the total shift
from all core electrons is $2.07\times 10^{7}$ MHz=8.57 $\cdot 10^{-2}$ eV,
which is $\sim$ 1% of the nuclear frequency.

Electronic correction to the nuclear frequency comes also from magnetic
interaction between electrons and nucleus. The first order gives ordinary
magnetic hyperfine splitting of the transition frequencies. The magnetic shift
is given by the second-order magnetic dipole hyperfine correction to the
energy

$\delta E_{g}^{\rm hfs}=\sum_{n}\frac{\langle g|\hat{H}^{\rm
hfs}|n\rangle^{2}}{E_{g}-E_{n}}$ (6)

Here index $g$ stands for the ground electronic state, $\hat{H}^{\rm hfs}$ is
the magnetic dipole hyperfine structure operator. Values of $\delta E_{g}^{\rm
hfs}$ are different for the ground and isomeric nuclear states since their
magnetic moments and spins are different. Magnetic moment values can be found
in Ref. Thm . In addition, there is the second order contribution from the
mixing of the ground and isomeric nuclear states by the magnetic filed of
electrons. Preliminary estimations show that the second order magnetic shift
is significantly smaller than the electronic shift considered in the present
work. More detailed analysis might be a subject of further work.

###### Acknowledgements.

This work was supported by the Australian Research Council Grants No.
DP230101058 and DP200100150.

## References

  * (1) E. Peik, T. Schumm, M. S. Safronova, A. Pálffy, J. Weitenberg, and P. G. Thirolf, Nuclear clocks for testing fundamental physics, Quantum Sci. Technol. 6, 034002 (2021).
  * (2) K. Beeks, T. Sikorsky, T. Schumm, J. Thielking, M. V. Okhapkin and E. Peik, The thorium-229 low-energy isomer and the nuclear clock, Nat. Rev. Phys. 3, 238 (2021).
  * (3) S. Kraemer, J. Moens, M. Athanasakis-Kaklamanakis, S. Bara, K. Beeks, P. Chhetri, K. Chrysalidis, A. Claessens, T. E. Cocolios, J. G. M. Correia, et al, Observation of the radiative decay of the 229Th nuclear clock isomer, Nature 617, 706 (2023).
  * (4) L. von der Wense, B. Seiferle, M. Laatiaoui, J. B. Neumayr, H.-J. Maier, H.-F. Wirth, C. Mokry, J. Runke, K. Eberhardt, C. E. Düllmann et al, Direct detection of the 229Th nuclear clock transition, Nature 533, 47 (2016).
  * (5) B. Seiferle, L. von der Wense, and P. G. Thirolf, Lifetime measurement of the 229mTh nuclear isomer, Phys. Rev. Lett. 118, 042501 (2017).
  * (6) B. Seiferle, L. von der Wense, P. V. Bilous, I. Amersdorffer, C. Lemell, F. Libisch, S. Stellmer, T. Schumm, C. E. Düllmann, A. Pálffy, and P. G. Thirolf, Energy of the 229Th nuclear clock transition, Nature 573, 243 (2019).
  * (7) A. Yamaguchi, H. Muramatsu, T. Hayashi, N. Yuasa, K. Nakamura, M. Takimoto, H. Haba, K. Konashi, M. Watanabe, H. Kikunaga, K. Maehata, N.?Y. Yamasaki,and K. Mitsuda, Energy of the 229Th nuclear clock isomer determined by absolute $\gamma$-ray energy difference, Phys. Rev. Lett. 123, 222501 (2019).
  * (8) T. Sikorsky, J. Geist, D. Hengstler, S. Kempf, L. Gastaldo, C. Enss, C. Mokry, J. Runke, C. E. Düllmann, P. Wobrauschek, et al, Measurement of the 229Th isomer energy with a magnetic microcalorimeter, Phys. Rev. Lett. 125, 142503 (2020).
  * (9) E. Peik and Chr. Tamm, Nuclear laser spectroscopy of the 3.5 eV transition in Th-229, Europhys. Lett. 61, 181 (2003).
  * (10) J. Thielking, M. V. Okhapkin, P. Glowacki, D. M. Meier, L. von der Wense, B. Seiferle, C. E. Düllmann, P. G. Thirolf, and E. Peik, Laser spectroscopic characterization of the nuclear-clock isomer 229mTh, Nature 556, 321 (2018). https://doi.org/10.1038/s41586-018-0011-8
  * (11) C. J. Campbell, A. G. Radnaev, A. Kuzmich, V. A. Dzuba, V. V. Flambaum, and A. Derevianko, Single-Ion Nuclear Clock for Metrology at the 19th Decimal Place, Phys. Rev. Lett. 108, 120802 (2012).
  * (12) V. V. Flambaum, Enhanced Effect of Temporal Variation of the Fine Structure Constant and the Strong Interaction in 229Th, Phys. Rev. Lett. 97, 092502 (2006).
  * (13) V. V. Flambaum, Enhancing the effect of Lorentz invariance and Einstein’s equivalence principle violation in nuclei and atoms, Phys. Rev. Lett. 117, 072501, (2016).
  * (14) J.C. Berengut, V.A. Dzuba, V.V. Flambaum, S.G. Porsev, Proposed experimental method to determine the alpha sensitivity of splitting between ground and 7.6 eV isomeric states in 229Th, Phys. Rev. Lett. 102, 210801 (2009).
  * (15) V.V. Flambaum, R.B. Wiringa, Enhanced effect of quark mass variation in 229Th and limits from Oklo data, Phys. Rev. C 79, 034302 (2009).
  * (16) E. Litvinova, H. Feldmeier, J. Dobaczewski, V.V. Flambaum, Nuclear structure of lowest 229Th states and time-dependent fundamental constants, Phys. Rev. C 79, 064303 (2009).
  * (17) Pavel Fadeev, Julian C. Berengut, and Victor V. Flambaum, Sensitivity of 229Th nuclear clock transition to variation of the fine-structure constant, Phys. Rev. A 102, 052833 (2020).
  * (18) P. Fadeev, J. C. Berengut, V. V. Flambaum, Effects of variation of the fine structure constant $\alpha$ and quark mass $m_{q}$ in Mössbauer nuclear transitions, Phys. Rev. C 105, L051303 (2022).
  * (19) A. Arvanitaki, J. Huang, and K. Van Tilburg, Searching for dilaton dark matter with atomic clock, Phys. Rev. D 91, 015015 (2015).
  * (20) Y. V. Stadnik, V. V. Flambaum, Can dark matter induce cosmological evolution of the fundamental constants of Nature? Phys. Rev. Lett. 115, 201301, (2015).
  * (21) A. Claessens, F. Ivandikov, S. Bara, P. Chhetri, A. Dragoun, Ch.E. Düllmann, Y. Elskens, R. Ferrer, S. Kraemer, Yu. Kudryavtsev, et al, Laser ionization scheme development for in-gas-jet spectroscopy studies of Th+, Nuclear Inst. and Methods in Physics Research B 540, 224 (2023).
  * (22) M. S. Safronova, S. G. Porsev, M. G. Kozlov, J. Thielking, M. V. Okhapkin,P. Glowacki, D. M. Meier, and E. Peik, Nuclear Charge Radii of 229Th from Isotope and Isomer Shifts, Phys. Rev. Lett. 121, 213001 (2018).
  * (23) Wade G. Rellergert, D. DeMille, R. R. Greco, M. P. Hehlen, J. R. Torgerson, and Eric R. Hudson, Constraining the evolution of the fundamental constants with a solid-state optical frequency reference based on the 229Th nucleus, Phys. Rev. Lett. 104, 200802 (2010).
  * (24) G. A. Kazakov, A. N. Litvinov, V. I. Romanenko, L. P. Yatsenko, A. V. Romanenko, M. Schreitl, G. Winkler, and T. Schumm, Performance of a 229Thorium solid-state nuclear clock, New J. Phys. 14, 083019 (2012).
  * (25) K. Beeks, T. Sikorsky, V. Rosecker, M. Pressler, F. Schaden, D. Werban, N. Hosseini, L. Rudischer, F. Schneider, P. Berwian, et al, Growth and characterization of thorium-doped calcium fluoride single crystals, Sci Rep 13, 3897 (2023). https://doi.org/10.1038/s41598-023-31045-5
  * (26) V. A. Dzuba, Combination of the single-double coupled cluster and the configuration interaction methods: application to barium, lutetium and their ions, Phys. Rev. A 90, 012517 (2014).
  * (27) V. A. Dzuba, V. V. Flambaum, P. G. Silvestrov, O. P. Sushkov, Correlation potential method for the calculation of energy levels, hyperfine structure and E1 transition amplitudes in atoms with one unpaired electron, J. Phys. B: At. Mol. Phys., 20, 1399-1412 (1987).
  * (28) J. Blaise and J.-F. Wyart, Energy Levels and Atomic Spectra of Actinides, in International Tables of Selected Constants, 20, 1 (Centre National de la Recherche Scientifique, Paris, France, 1992).
  * (29) I. Angeli and K. P. Marinova, Table of experimental nuclear ground state charge radii, At. Data Nucl. Data Tables 99, 69 (2013).


# Variety of general position problems in graphs

Jing Tian a,b Sandi Klavžar b,c,d

a School of Science, Zhejiang University of Science and Technology,
Hangzhou, Zhejiang 310023, PR China
<EMAIL_ADDRESS>
b Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia
cFaculty of Mathematics and Physics, University of Ljubljana, Slovenia
d Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia
<EMAIL_ADDRESS>

###### Abstract

Let $X$ be a vertex subset of a graph $G$. Then $u,v\in V(G)$ are
$X$-positionable if $V(P)\cap X\subseteq\\{u,v\\}$ holds for any shortest
$u,v$-path $P$. If each two vertices from $X$ are $X$-positionable, then $X$
is a general position set. The general position number of $G$ is the
cardinality of a largest general position set of $G$ and has been already well
investigated. In this paper a variety of general position problems is
introduced based on which natural pairs of vertices are required to be
$X$-positionable. This yields the total (resp. dual, outer) general position
number. It is proved that the total general position sets coincide with sets
of simplicial vertices, and that the outer general position sets coincide with
sets of mutually maximally distant vertices. It is shown that a general
position set is a dual general position set if and only if its complement is
convex. Several sufficient conditions are presented that guarantee that a
given graph has no dual general position set. The total general position
number, the outer general position number, and the dual general position
number of arbitrary Cartesian products are determined.

Keywords: general position; total general position; outer general position;
dual general position; Cartesian product of graphs; strong resolving graph;
convex subgraph

AMS Subj. Class. (2020): 05C12, 05C69, 05C76

##  1 Introduction

General position sets were introduced to graph theory independently in [3,
18], but in the special case of hypercubes, these sets had been studied
previously in [15]. Finding a largest general position set in a graph $G$ is
an NP-hard problem [18]. In [2], a characterization of general position sets
in graphs was proved and the general position number for the complement of
bipartite graphs, the complement of trees, and the complement of hypercubes
was determined. Afterwards, general position sets received a wide attention,
see [7, 9, 12, 14, 19] for a selection of recent developments.

Mutual-visibility sets are closely related to general position sets and were
recently introduced by Di Stefano [6]. While investigating mutual-visibility
sets in strong products, there was a natural need to introduce total mutual-
visibility sets [5]. This has led to the variety of mutual-visibility sets
which was formalized in [4]. Motivated by the variety of mutual-visibility
sets, the main purpose of this paper is to introduce and study the
corresponding variety of general position sets. It consists of general
position sets, total general position sets, outer general position sets, and
dual general position sets.

The rest of the paper is organized as follows. In the rest of the introduction
we give definitions needed. In the next section we introduce the variety of
the general position sets and characterize total general position sets and
outer general position sets. In Section 3 we focus on dual general position
sets. We first observe that a general position set is a dual general position
set if and only if its complement is convex. Then we consider graphs with
small dual general position numbers. In particular, several sufficient
conditions are presented that guarantee that a given graph has no dual general
position set at all. In Section 4 we determine the total general position
number, the outer general position number, and the dual general position
number of arbitrary Cartesian products.

For a natural number $n$ we set $[n]=\\{1,\ldots,n\\}$. All graphs
$G=(V(G),E(G))$ in the paper are connected unless otherwise stated. The order
of $G$ is the value of $|V(G)|$. The open neighborhood of a vertex $u$ of $G$
is denoted by $N_{G}(u)$. The degree of a vertex $u$ of $G$ is
$\deg_{G}(u)=|N_{G}(u)|$. If $X\subseteq V(G)$, then $G[X]$ denotes the
subgraph of $G$ induced by $X$. Moreover, $G-X$ is the subgraph of $G$
obtained from $G$ by deleting all vertices from $X$. If $G$ is not a tree,
then its girth $g(G)$ is the length of a shortest cycle of $G$. A vertex of
$G$ is simplicial if its neighbourhood induces a complete subgraph. The set of
simplicial vertices of $G$ will be denoted by $S(G)$ and the cardinality of
$S(G)$ by $s(G)$. The clique number of $G$ is denoted by $\omega(G)$.

The distance $d_{G}(u,v)$ between vertices $u$ and $v$ of $G$ is the usual
shortest-path distance. The diameter ${\rm diam}(G)$ of $G$ is the maximum
distance between pairs of vertices of $G$. A subgraph $G^{\prime}$ of a graph
$G$ is _isometric_ , if for every two vertices $x$ and $y$ of $G^{\prime}$ we
have $d_{G^{\prime}}(x,y)=d_{G}(x,y)$. A subgraph $G^{\prime}$ of a graph $G$
is _convex_ , if for every two vertices of $G^{\prime}$, every shortest path
in $G$ between them lies completely in $G^{\prime}$. By abuse of language we
also say that a set of vertices is convex if it induces a convex subgraph.

The Cartesian product $G\,\square\,H$ of graphs $G$ and $H$ has the vertex set
$V(G\,\square\,H)=V(G)\times V(H)$, and vertices $(g,h$) and
$(g^{\prime},h^{\prime})$ are adjacent if either $gg^{\prime}\in E(G)$ and
$h=h^{\prime}$, or $g=g^{\prime}$ and $hh^{\prime}\in E(H)$. The direct
product $G\times H$ has the same vertex set as $G\,\square\,H$, while vertices
$(g,h$) and $(g^{\prime},h^{\prime})$ are adjacent if $gg^{\prime}\in E(G)$
and $hh^{\prime}\in E(H)$. The strong product $G\boxtimes H$ also has the same
vertex set as $G\,\square\,H$, while $E(G\boxtimes H)=E(G\,\square\,H)\cup
E(G\times H)$. The join $G\oplus H$ is the graph obtained from the disjoint
union of $G$ and $H$ by adding all possible edges between vertices from $G$
and vertices from $H$.

##  2 The variety

In this section we first introduce the announced variety of general position
sets. After that we characterize total general position sets and outer general
position sets.

Let $G=(V(G),E(G))$ be a graph and $X\subseteq V(G)$. Vertices $u,v\in V(G)$
are $X$-positionable if for any shortest $u,v$-path $P$ we have $V(P)\cap
X\subseteq\\{u,v\\}$. Note that each pair of adjacent vertices is
$X$-positionable. Set $\overline{X}=V(G)\setminus X$. Then we say that $X$ is

  * •

a _general position set_ , if every $u,v\in X$ are $X$-positionable;

  * •

a _total general position set_ , if every $u,v\in V(G)$ are $X$-positionable;

  * •

an _outer general position set_ , if every $u,v\in X$ are $X$-positionable,
and every $u\in X$, $v\in\overline{X}$ are $X$-positionable; and

  * •

a _dual general position set_ , if every $u,v\in X$ are $X$-positionable, and
every $u,v\in\overline{X}$ are $X$-positionable.

The cardinality of a largest general position set, a largest total general
position set, a largest outer general position set, and a largest dual general
position set will be respectively denoted by ${\rm gp}(G)$, ${\rm gp}_{\rm
t}(G)$, ${\rm gp}_{\rm o}(G)$, and ${\rm gp}_{\rm d}(G)$. Also, these graph
invariants will be respectively called the general position number, the total
general position number, the outer general position number, and the dual
general position number of $G$. Moreover, for any invariant $\tau(G)$ from the
above ones, by a $\tau$-set we mean any set of vertices of cardinality
$\tau(G)$. In addition, for any two invariants $\tau_{1}(G)$ and
$\tau_{2}(G)$, by a $(\tau_{1},\tau_{2})$-graph we mean any graph $G$ with
$\tau_{1}(G)=\tau_{2}(G)$.

If $G$ is a graph, then by definition,

$\displaystyle{\rm gp}(G)$ $\displaystyle\geq{\rm gp}_{\rm o}(G)\geq{\rm
gp}_{\rm t}(G)\quad{\rm and}$ (1) $\displaystyle{\rm gp}(G)$
$\displaystyle\geq{\rm gp}_{\rm d}(G)\geq{\rm gp}_{\rm t}(G)\,.$ (2)

If $G$ is a block graph, then ${\rm gp}(G)=s(G)$, see [18, Theorem 3.6].
Moreover, we can check directly that the set of simplicial vertices of $G$ is
also a total general position set. Hence block graphs are $({\rm gp},{\rm
gp}_{\rm t})$-graphs. Having (1) and (2) in mind we thus get that if $G$ is a
block graph, then

${\rm gp}(G)={\rm gp}_{\rm o}(G)={\rm gp}_{\rm d}(G)={\rm gp}_{\rm
t}(G)=s(G)\,.$

In particular, if $n\geq 2$, then $\tau(P_{n})=2$ for each $\tau\in\\{{\rm
gp},{\rm gp}_{\rm o},{\rm gp}_{\rm d},{\rm gp}_{\rm t}\\}$. Moreover,

  * •

each pair of distinct vertices of $P_{n}$ forms a ${\rm gp}$-set of $P_{n}$,

  * •

$\\{1,n\\}$ is the only ${\rm gp}_{\rm o}$-set of $P_{n}$,

  * •

$\\{1,2\\}$, $\\{1,n\\}$, and $\\{n-1,n\\}$ are the only ${\rm gp}_{\rm
d}$-sets of $P_{n}$,

  * •

$\\{1,n\\}$ is the only ${\rm gp}_{\rm t}$-set of $P_{n}$.

Contrary to block graphs, by considering Cartesian products of two complete
graphs we will see that all these four parameters can be pairwise arbitrary
different.

We now characterize total general position sets as follows.

###### Theorem 2.1

Let $G$ be a graph and $X\subseteq V(G)$. Then $X$ is a total general position
set of $G$ if and only if $X\subseteq S(G)$. Moreover, ${\rm gp}_{\rm
t}(G)=s(G)$.

Proof. Assume first that $X$ is a total general position set of $G$ and
consider an arbitrary vertex $x$ from $X$. Suppose that $x\not\in S(G)$. Then
$x$ has two adjacent vertices $y$ and $z$ such that $d_{G}(y,z)=2$, which
means that there exists a shortest $y,z$-path containing $x$. Hence the
vertices $y$ and $z$ are not $X$-positionable, a contradiction. As a
consequence, we conclude that $x$ must belong to $S(G)$ and then $X\subseteq
S(G)$.

To prove the converse, assume that $X\subseteq S(G)$. Consider any two
vertices $u$ and $v$ from $V(G)$ and let $P_{uv}$ be a shortest $u,v$-path of
$G$. If $u$ is adjacent to $v$, then $V(P_{uv})=\\{u,v\\}$ and hence $u$ and
$v$ are $X$-positionable. Assume next that $d_{G}(u,v)\geq 2$. Let $P_{uv}$ be
the path $u=x_{1},x_{2},\ldots,x_{k}=v$. Then $k\geq 3$. Suppose that
$x_{i}\in X$, where $2\leq i\leq k-1$. Since $x_{i}$ is a simplicial vertex of
$G$, $x_{i-1}$ must be adjacent to $x_{i+1}$ and hence
$x_{1},\ldots,x_{i-1},x_{i+1},\ldots,x_{k}$ is a $u,v$-path shorter than
$P_{uv}$. Since this is not possible, $V(P_{uv})\cap X\subseteq\\{u,v\\}$, and
thus $u$ and $v$ are $X$-positionable. Hence $X$ is a total general position
set of $G$, and then we can conclude that ${\rm gp}_{\rm t}(G)=s(G)$.
$\square$

###### Corollary 2.2

If $G$ is a graph, then ${\rm gp}_{\rm t}(G)=0$ if and only $G$ has no
simplicial vertices.

We continue with a characterization of outer general position sets. For this
sake, the following concepts are crucial. A vertex $u$ of a graph $G$ is
_maximally distant_ from $v\in V(G)$ if for every $w\in N_{G}(u)$ it holds
$d_{G}(v,w)\leq d_{G}(u,v)$. If also $v$ is maximally distant from $u$, then
$u$ and $v$ are said to be _mutually maximally distant_. The strong resolving
graph $G{}_{\rm SR}$ of $G$ has $V(G{}_{\rm SR})=V(G)$ and two vertices being
adjacent in $G{}_{\rm SR}$ if they are mutually maximally distant in $G$. This
notion was introduced in [20] as a tool to study the strong metric dimension.
The paper [17] gives a survey on strong resolving graphs with an emphasize on
the realization problem (which graphs have a given graph as their strong
resolving graph) and the characterization problem (characterize graphs that
are strong resolving graphs of some graphs). From our perspective, in [10] it
was proved that ${\rm gp}(G)\geq\omega(G{}_{\rm SR})$ holds for any connected
graph $G$.

Now we can characterize outer general position sets as follows.

###### Theorem 2.3

Let $G$ be a connected graph and $X\subseteq V(G)$, $|X|\geq 2$. Then $X$ is
an outer general position set of $G$ if and only if each pair of vertices from
$X$ is mutually maximally distant. Moreover,

${\rm gp}_{\rm o}(G)=\omega(G{}_{\rm SR})\,.$

Proof. Let $X\subseteq V(G)$ be a set with $|X|\geq 2$.

Assume first that $X$ is an outer general position set of $G$ and let $x,y\in
X$. If $x$ and $y$ are not mutually maximally distant, there exists (at least)
one neighbor of $x$ or $y$, say $w\in N_{G}(x)$, such that
$d_{G}(w,y)=d_{G}(x,y)+1$. Hence there exists a shortest $w,y$-path which
contains $x$. Then no matter whether $w\in X$ or $w\notin X$, this contradicts
the fact that $\\{x,y\\}\subseteq X$ is an outer general position set.

Conversely, assume that any two vertices from $X$ are mutually maximally
distant. Consider any two vertices $u$ and $v$. If $u,v\in X$, the internal
vertices of all shortest $u,v$-paths are not from $S$ as $u$ and $v$ are
mutually maximally distant. Hence $u$ and $v$ are $X$-positionable. Assume
next that, without loss of generality, $u\in X$ and $v\in V(G)\setminus X$. If
there exists a vertex $w\in X\setminus\\{u\\}$ lying on a shortest $u,v$-path,
then $u$ and $w$ are not mutually maximally distant. Hence $u,v$ are
$X$-positionable.

The formula ${\rm gp}_{\rm o}(G)=\omega(G{}_{\rm SR})$ now follows by the
above characterization of outer general position sets and by the definition of
the strong resolving graph. $\square$

###### Corollary 2.4

If $G$ is a connected graph of order at least $2$, then ${\rm gp}_{\rm
o}(G)\geq 2$.

Proof. Let $u$ and $v$ be vertices of $G$ such that $d_{G}(u,v)={\rm
diam}(G)$. Then $u$ and $v$ are mutually maximally distant, hence ${\rm
gp}_{\rm o}(G)\geq 2$ by Theorem 2.3. $\square$

As already mentioned, it was proved in [10] that ${\rm
gp}(G)\geq\omega(G{}_{\rm SR})$ holds for any connected graph $G$. Hence by
Theorem 2.3 we have

${\rm gp}(G)\geq\omega(G{}_{\rm SR})={\rm gp}_{\rm o}(G)\,.$

Thus, knowing that ${\rm gp}(G)=\omega(G{}_{\rm SR})$ holds for some graph
$G$, we also know ${\rm gp}_{\rm o}(G)$. For instance, [10, Proposition 4.5]
asserts that if $r_{1}\geq t_{1}\geq 1$ and $r_{2}\geq t_{2}\geq 1$, then

${\rm gp}(K_{r_{1},t_{1}}\boxtimes
K_{r_{2},t_{2}})=r_{1}r_{2}=\omega((K_{r_{1},t_{1}}\boxtimes
K_{r_{2},t_{2}}){}_{\rm SR})\,,$

which in turn implies that

${\rm gp}_{\rm o}(K_{r_{1},t_{1}}\boxtimes K_{r_{2},t_{2}})=r_{1}r_{2}\,.$

##  3 Dual general position sets

From Theorem 2.1 it follows that if $X$ is a total general position set of
$G$, then each subset of $X$ is also a total general position set of $G$.
Similarly, by Theorem 2.3 this hereditary property also holds for outer
general position sets. In addition, this property is also known to hold for
general position sets. A bit surprisingly, if $X$ is a dual general position
set of $G$ and $Y\subseteq X$, then $Y$ need not be a dual general position
set of $G$. To see this, consider two adjacent vertices of $C_{5}$ which form
a dual general position set, however, one vertex of $C_{5}$ does not form such
a set. So each of the properties of being in general position, being in total
general position, and being in outer general position is hereditary, but the
property of being in dual general position property is not.

The above consideration indicates that the dual general position is
intrinsically different from the other three invariants. In this section we
have a closer look to it. We first characterize which general position sets
are dual general position sets. Then we respectively consider graphs $G$ with
${\rm gp}_{\rm d}(G)=0$, ${\rm gp}_{\rm d}(G)=1$, and ${\rm gp}_{\rm d}(G)\geq
2$.

Let $X$ be a dual general position set in a graph $G$. Then, clearly, $X$ is a
general position set. Hence to find a largest dual general position set in $G$
if suffices to check all general position sets in $G$ and check if they are
also dual. For this task, the following result is useful.

###### Theorem 3.1

Let $X$ be a general position set of a graph $G$. Then $X$ is a dual general
position set if and only if $G-X$ is convex.

Proof. Assume that $X$ is a dual general position set. Let $x,y\in
V(G)\setminus X$ and let $P$ be a shortest $x,y$-path. Since $X$ is a dual
general position set, the vertices $x$ and $y$ are $X$-positionable which in
turn implies that $V(P)\cap X=\emptyset$. It follows that $G-X$ is convex.

Conversely, assume that $X$ is a general position set and $G-X$ is convex. If
$x,y\in X$, then $x$ and $y$ are $X$-positionable since $X$ is a general
position set. Consider next $x,y\in V(G)\setminus X$. Since $G-X$ is convex,
each shortest $x,y$-path lies in $G-X$ hence no such path contains vertices
from $X$. We can conclude that $X$ is a dual general position set. $\square$

For the later use we state explicitly the following consequence of Theorem
3.1.

###### Corollary 3.2

If $G$ is a graph and $X\subseteq S(G)$, then $X$ is a dual general position
set.

Proof. Since $X\subseteq S(G)$ we see that $X$ is a general position set and
also that $G-X$ is convex. Hence the assertion follows by Theorem 3.1.
$\square$

###  3.1 Graphs $G$ with ${\rm gp}_{\rm d}(G)=0$

In this subsection we focus on graphs $G$ with ${\rm gp}_{\rm d}(G)=0$. It
follows from Theorem 3.1 that ${\rm gp}_{\rm d}(G)=0$ if and only if for every
general position set $X$ the subgraph $G-X$ is not convex in $G$. Since dual
general position sets are not hereditary (recall the example of $C_{5}$), we
must consider all general position sets, not only singletons.

We say that an edge $e$ of a graph $G$ is $P_{4}$-inner isometric, if $e$ is
the middle edge of some isometric $P_{4}$.

###### Proposition 3.3

Let $G$ be a connected graph. If each edge of $G$ is $P_{4}$-inner isometric,
then ${\rm gp}_{\rm d}(G)=0$.

Proof. Assume that $G$ is a graph in which each edge is $P_{4}$-inner
isometric. Then clearly $\delta(G)\geq 2$. Suppose on the contrary that ${\rm
gp}_{\rm d}(G)\geq 1$ and let $x$ be a vertex of $G$ from some dual general
position set $X$. Let $y$ be a neighbor of $x$. From our assumption, the edge
$xy$ is $P_{4}$-inner isometric and let $x^{\prime},x,y,y^{\prime}$ be the
vertices of an isometric $P_{4}$, denote it by $Q$, where $x^{\prime}x\in
E(G)$ and $yy^{\prime}\in E(G)$. Then at least one of the vertices
$x^{\prime}$ and $y$ belongs to $X$, for otherwise $x^{\prime}$ and $y$ are
not $X$-positionable.

Suppose first that $y\in X$. It implies that $y^{\prime}\not\in X$ for
otherwise $x$ and $y^{\prime}$ are not $X$-positionable. Analogously,
$x^{\prime}\not\in X$ also holds. But then the vertices $x^{\prime}$ and
$y^{\prime}$ are not $X$-positionable.

Suppose second that $x^{\prime}\in X$. Then $y\notin X$, for otherwise $y$ and
$x^{\prime}$ are not $X$-positionable. Consider now an isometric $P_{4}$, say
$R$, such that the edge $x^{\prime}x$ is the middle edge of $R$. Let $R$ be
the path on the vertices $z^{\prime},x^{\prime},x,z$, where
$z^{\prime}x^{\prime}\in E(G)$ and $xz\in E(G)$. Since $x,x^{\prime}\in X$ we
see that $z^{\prime}\notin X$ and $z\notin X$. Since $Q$ is isometric, we have
$z^{\prime}\neq y$ and $z^{\prime}\neq y^{\prime}$. If $z=y$, then
$z^{\prime}$ and $z=y$ are not $X$-positionable. Similarly, if $z\neq y$, then
again $z^{\prime}$ and $z$ are not $X$-positionable. This final contradiction
implies that ${\rm gp}_{\rm d}(G)=0$. $\square$

###### Corollary 3.4

Let $G$ be a connected graph with $g(G)\geq 6$. Then ${\rm gp}_{\rm d}(G)=0$
if and only if $\delta(G)\geq 2$.

Proof. If $\delta(G)=1$ and $u$ is a pendant vertex of $G$, then $\\{u\\}$ is
a dual general position set, hence ${\rm gp}_{\rm d}(G)\geq 1$.

To prove the other direction, assume that $\delta(G)\geq 2$. Since $g(G)\geq
6$ we see that each edge of $G$ is $P_{4}$-inner isometric. Proposition 3.3
yields the conclusion. $\square$

Next, we give an infinite family of graphs whose dual general position number
is zero, yet none of their edges is $P_{4}$-inner isometric. Let $m\geq 5$ and
consider the join graph $G_{m}=P_{m}\oplus 2K_{1}$, see Fig. 1.

$x$$x^{\prime}$$p_{1}$$p_{m}$ Figure 1: The graph $G_{m}$.

It is readily verified that no edge of $G_{m}$ is $P_{4}$-inner isometric. On
the other hand, the following holds.

###### Proposition 3.5

If $m\geq 5$, then ${\rm gp}_{\rm d}(G_{m})=0$.

Proof. Set $G_{m}=P_{m}\oplus 2K_{1}$, let $V(P_{m})=\\{p_{1},\ldots,p_{m}\\}$
with natural adjacencies, and let $V(2K_{1})=\\{x,x^{\prime}\\}$, see Fig. 1
again.

Let $X$ be an arbitrary dual general position set of $G_{m}$. If
$x,x^{\prime}\not\in X$, then $X=\emptyset$ for otherwise $x$ and $x^{\prime}$
are not $X$-positionable. In the rest we may hence assume without loss of
generality that $x\in X$, for otherwise we are done.

We first claim that $x^{\prime}\notin X$. Indeed, otherwise no vertex $p_{i}$,
$i\in[m]$, lies in $X$, but then no two vertices $p_{i}$ and $p_{j}$,
$|i-j|\geq 2$, are not $X$-positionable. Further and similarly, we have
$\\{p_{1},\ldots,p_{m}\\}\cap X\neq\emptyset$. Hence there exists $i\in[m]$
such that $p_{i}\in X$. Select and fix $i$ to be the smallest such index. Then
by the symmetry we may assume that $1\leq i\leq\lceil m/2\rceil$. We now
distinguish two cases.

Suppose first that $i=1$. Then it follows that $p_{j}\not\in X$ for $3\leq
j\leq m$. Since $m\geq 5$, the vertex $x$ lies in the middle of a shortest
$p_{3},p_{m}$-path, hence the vertices $p_{3}$ and $p_{m}$ are not
$X$-positionable.

Suppose second that $2\leq i\leq\lceil m/2\rceil$. By the way $i$ is selected
and by the symmetry we have $p_{1}\notin X$ and $p_{m}\notin X$. But then
$p_{1}$ and $p_{m}$ are not $X$-positionable. $\square$

For the cycles $C_{4}$ and $C_{5}$, it is observed that ${\rm gp}_{\rm
d}(C_{4})={\rm gp}_{\rm d}(C_{5})=2$. These graphs can be considered as
special cases of generalized theta graphs which are defined as follows. For
positive integers $1\leq\ell_{1}\leq\cdots\leq\ell_{k}$ and $\ell_{2}\geq 2$,
the generalized theta graph $\Theta(\ell_{1},\ldots,\ell_{k})$ is obtained by
joining two vertices $a$ and $b$ with $k$ internally disjoint paths of lengths
$\ell_{1},\ldots,\ell_{k}$.

###### Proposition 3.6

Let $1\leq\ell_{1}\leq\cdots\leq\ell_{k}$, where $k\geq 2$, $\ell_{2}\geq 2$.
Then ${\rm gp}_{\rm d}(\Theta(\ell_{1},\ldots,\ell_{k}))=0$ if and only if one
of the following cases holds:

  1. (i)

$k=2$, $\ell_{1}+\ell_{2}\geq 6$;

  2. (ii)

$k\geq 3$, $\ell_{1}=1$, $\ell_{2}\geq 5$;

  3. (iii)

$k\geq 3$, $\ell_{1}=2$, and $\ell_{i}\neq 3$ for $2\leq i\leq k$;

  4. (iv)

$k\geq 3$, $\ell_{1}\geq 3$.

Proof. Set $\Theta=\Theta(\ell_{1},\ldots,\ell_{k})$ for the rest of the proof
and let $Q_{1},\ldots,Q_{k}$ be the internally disjoint paths of lengths
$\ell_{1},\ldots,\ell_{k}$ of $\Theta$ connecting $a$ and $b$.

$(i)$ If $k=2$ and $\ell_{1}+\ell_{2}\leq 5$, then
$\Theta\in\\{C_{3},C_{4},C_{5}\\}$, hence ${\rm gp}_{\rm d}(\Theta)\geq 2$. On
the other hand, if $\ell_{1}+\ell_{2}\geq 6$, then $\Theta$ is a cycle of
order at least $6$ and thus each edge of $\Theta$ is $P_{4}$-inner isometric.
Hence ${\rm gp}_{\rm d}(\Theta)=0$ by Proposition 3.3.

$(ii)$ Let $k\geq 3$ and $\ell_{1}=1$. Assume first that $\ell_{2}\leq 4$. If
$\ell_{2}=2$, then the middle vertex of $Q_{2}$ is simplicial and by Corollary
3.2, $\\{x\\}$ is a dual general position set and so ${\rm gp}_{\rm
d}(\Theta)\geq 1$. If $\ell_{2}=3$, then $\Theta[Q_{1}\cup Q_{2}]\cong C_{4}$.
Let $u$ and $v$ be the internal vertices of $Q_{2}$. Then we infer that
$\Theta-\\{u,v\\}$ is convex and using Theorem 3.1 we get ${\rm gp}_{\rm
d}(\Theta)\geq 2$. Similarly, we get that ${\rm gp}_{\rm d}(\Theta)\geq 2$ if
$\ell_{2}=4$. Assume finally that $\ell_{2}\geq 5$. Then each edge of $\Theta$
is $P_{4}$-inner isometric. By Proposition 3.3 we thus have ${\rm gp}_{\rm
d}(\Theta)=0$.

$(iii)$ Let $k\geq 3$ and $\ell_{1}=2$. Assume first that there exists an
index $i$ such that $\ell_{i}=3$ and let $i$ be the smallest such index. Note
that $i\geq 2$. If $x_{i}$ and $x_{i}^{\prime}$ are the two internal vertices
of $Q_{i}$, then $\Theta-\\{x_{i},x_{i}^{\prime}\\}$ is convex, hence Theorem
3.1 implies that ${\rm gp}_{\rm d}(\Theta)\geq 2$.

Assume second that $\ell_{i}\neq 3$ for each $2\leq i\leq k$. If
$\ell_{1}=\cdots=\ell_{k}=2$, then $\Theta\cong K_{2,k}$. A possible dual
general position set wound need to contain two adjacent vertices of each
$4$-cycle, but this is not possible. So ${\rm gp}_{\rm d}(K_{2,k})=0$ for
$k\geq 3$. Let next $j$ be the smallest index such that $\ell_{j}\geq 4$, so
that $\ell_{1}=\cdots=\ell_{j-1}=2$. (It is possible that $j=2$.) Then the
subgraph of $\Theta$ induced by $Q_{1}\cup\cdots\cup Q_{j-1}$ is isomorphic to
$K_{2,j-1}$ and we readily see that no vertex from it can lie in a dual
general position set. In addition, the vertices from $Q_{1}\cup
Q_{j^{\prime}}$, where $j^{\prime}\geq j$, induce an isometric cycle of
$\Theta$ of order at least $6$, from which we conclude that none of the
vertices from the cycle can lie in a dual general position set. We conclude
that ${\rm gp}_{\rm d}(\Theta)=0$.

$(iv)$ In this case we have $g(\Theta)\geq 6$, hence the assertion follows by
Corollary 3.4. $\square$

###  3.2 Graphs $G$ with ${\rm gp}_{\rm d}(G)=1$

We next consider graphs $G$ with ${\rm gp}_{\rm d}(G)=1$.

###### Proposition 3.7

If $G$ is a connected graph with ${\rm gp}_{\rm d}(G)=1$, then $s(G)=1$.

Proof. Let $G$ be a connected graph with ${\rm gp}_{\rm d}(G)=1$ and let
$\\{x\\}$ be a ${\rm gp}_{\rm d}$-set of $G$. Suppose first that $s(G)=0$.
Then it follows that the order of $G$ at least $4$ as each of the smaller
graphs contains at least one simplicial vertex. In particular, since $x$ is
not simplicial, it has two neighbors, say $x^{\prime}$ and $x^{\prime\prime}$,
such that $d_{G}(x^{\prime},x^{\prime\prime})=2$. But then $x^{\prime}$ and
$x^{\prime\prime}$ are not $\\{x\\}$-positionable. This contradiction implies
that $s(G)\geq 1$. On the other hand, Corollary 3.2 yields that $s(G)\leq 1$
and we are done. $\square$

The converse of Proposition 3.7 is not true. For a sporadic example consider
the graph $G$ obtained from $C_{4}$ by attaching a pendant vertex to one of
the vertices of $C_{4}$. Then ${\rm gp}_{\rm d}(G)=2\neq 1$ but $s(G)=1$. An
infinite family of such examples is the following. For integers $k\geq 1$ and
$\ell\geq 4$, let $G_{k,\ell}$ be the graph consisting of a chain of $k$
cycles $C_{\ell}$ which share vertices such that for an intermediate
$C_{\ell}$ its vertices of degree $3$ are its diametral vertices. Finally
attach a pendant vertex to a degree $2$ vertex of the last cycle. In Fig. 2
the graphs $G_{6,4}$ and $G_{6,5}$ are shown.

$j$$i$$i^{\prime}$$j^{\prime}$$v$$u$ Figure 2: Graphs $G_{6,4}$ and $G_{6,5}$
and their largest dual general position sets.

###### Proposition 3.8

If $k\geq 1$ and $\ell\geq 4$, then

${\rm gp}_{\rm d}(G_{k,\ell})=\left\\{\begin{array}[]{ll}1;&\ell\geq 6\,,\\\
2;&\ell=4\,,\\\ 3;&\ell=5\,.\\\ \end{array}\right.$

Proof. Let $e=uv$ be the pendent edge of $G_{k,\ell}$, where $u$ is the
pendant vertex. Since $u$ is a simplicial vertex of $G_{k,\ell}$, Corollary
3.2 implies ${\rm gp}_{\rm d}(G_{k,\ell})\geq 1$.

Assume first $\ell\geq 6$. Since $g(G_{k,\ell})\geq 6$ and each edge of
$G_{k,\ell}-u$ is $P_{4}$-inner isometric, no vertex of $G_{k,\ell}-u$ lies in
a dual general position set of $G_{k,\ell}$, cf. Corollary 3.4. Hence we have
${\rm gp}_{\rm d}(G_{k,\ell})\leq 1$ and thus ${\rm gp}_{\rm
d}(G_{k,\ell})=1$.

Assume second $\ell=4$. Let $i,i^{\prime},j,j^{\prime}$ be the vertices of the
first $C_{4}$ as indicated in Fig. 2. Since $\\{i,i^{\prime}\\}$ is a general
position set of $G_{k,\ell}$ and $G_{k,\ell}-\\{i,i^{\prime}\\}$ is convex,
Theorem 3.1 implies that ${\rm gp}_{\rm d}(G_{k,\ell})\geq 2$. Suppose on the
contrary that ${\rm gp}_{\rm d}(G_{k,\ell})\geq 3$ and let $X$ be an arbitrary
${\rm gp}_{\rm d}$-set of $G_{k,\ell}$.

Assume that $X$ contains a vertex $x$ with $\deg_{G_{k,\ell}}(x)=4$. Then at
least three neighbors of $x$ lie in $X$ for, otherwise two neighbors of $x$
are not $X$-positionable. But then again two neighbors of $x$ are not
$X$-positionable. By a parallel argument we also see that $X$ does not contain
the vertex of degree $3$. It follows that each vertex of $X$ is of degree at
most $2$.

We claim that $u\notin X$. Since $|X|\geq 3$, there exist $y,y^{\prime}\in X$
such that $\deg_{G_{k,\ell}}(y)=\deg_{G_{k,\ell}}(y^{\prime})=2$. (It is
possible $y,y^{\prime}\in\\{i,i^{\prime},j\\}$.) If $y$ and $y^{\prime}$ are
adjacent, then we may without loss of generality assume that $y=i$ and
$y^{\prime}=i^{\prime}$. But then $i^{\prime}$ and $u$ are not
$X$-positionable, so this cannot happen. Assume next that $y$ and $y^{\prime}$
are not adjacent. Let $z$ and $z^{\prime}$ be the two neighbors of $y$. It is
clear that $z$ and $z^{\prime}$ are not $X$-positionable if $y$ and
$y^{\prime}$ lie on the same cycle $C_{4}$. And if $y$ and $y^{\prime}$ are
not on the same $4$-cycle, then either $y$ lies on a shortest
$u,y^{\prime}$-path or $y^{\prime}$ lies on the shortest $u,y$-path. We
conclude that indeed $u\notin X$.

We have thus proved that $\deg_{G_{k,\ell}}(x)=2$ for each $x\in X$. Let $x$
and $x^{\prime}$ be two arbitrary vertices from $X$. By the same argument as
used in the previous paragraph we get that $xx^{\prime}\in E(G_{k,\ell})$. As
there are only two such edges possible, that is, $ii^{\prime}$ and
$i^{\prime}j$, and as $\\{i,i^{\prime},j\\}$ is not a dual general position
set, we can conclude that $\\{i,i^{\prime}\\}$ is a largest dual general
position set and so ${\rm gp}_{\rm d}(G_{k,\ell})=2$.

The argument for the case $\ell=5$ is similar and left to the reader.
$\square$

###  3.3 Graphs $G$ with ${\rm gp}_{\rm d}(G)\geq 2$

We next consider when a set of cardinality two forms a dual general position
set. In the next result we deduce a characterization (additional to the one of
Theorem 3.1) for two adjacent vertices.

###### Theorem 3.9

If $x$ and $y$ are two adjacent vertices of a graph $G$, then the following
statements are equivalent.

  1. (i)

$\\{x,y\\}$ is a dual general position set of $G$;

  2. (ii)

$G-\\{x,y\\}$ is convex;

  3. (iii)

For each $u,v\in N_{G}(x)\cup N_{G}(y)$ we have $d_{G}(u,v)\leq 2$, and the
graphs $G[N_{G}(x)-\\{y\\}]$ and $G[N_{G}(y)-\\{x\\}]$ are complete.

Proof. Let $X=N_{G}(x)-\\{y\\}$ and $Y=N_{G}(y)-\\{x\\}$.

$(i)\Rightarrow(ii)$: If $\\{x,y\\}$ is a dual general position set of $G$, it
follows from Theorem 3.1 that $G-\\{x,y\\}$ is convex.

$(ii)\Rightarrow(iii)$: Assume that $G-\\{x,y\\}$ is convex. Then $G[X]$ is
complete. Indeed, for otherwise two nonadjacent vertices $x^{\prime}$ and
$x^{\prime\prime}$ from $X$ are not $\\{x,y\\}$-positionable. Analogously,
$G[Y]$ is complete. Furthermore, if $u\in X$ and $v\in Y$, then
$d_{G}(u,v)\leq 3$. But if $d_{G}(u,v)=3$, then $G-\\{x,y\\}$ is not convex,
hence we conclude that $d_{G}(u,v)\leq 2$ for any $u,v\in N_{G}(x)\cup
N_{G}(y)$.

$(iii)\Rightarrow(i)$: Let $1\leq d_{G}(u,v)\leq 2$ for any two vertices
$u,v\in N_{G}(x)\cup N_{G}(y)$, and let $G[X]$ and $G[Y]$ be complete. Set
$G^{\prime}=G-\\{x,y\\}$. Consider two arbitrary distinct vertices $p$ and $q$
from $G^{\prime}$. We claim that no shortest $p,q$-path passes $x$ or $y$. Let
$Q$ be an arbitrary shortest $p,q$-path. Suppose first that
$V(Q)\cap\\{x,y\\}=\\{x\\}$. Then $Q$ contains two neighbors of $x$ but since
$G[X]$ is complete, this is a contradiction. The case when
$V(Q)\cap\\{x,y\\}=\\{y\\}$ is ruled out analogously. In the remaining case
suppose that $V(Q)\cap\\{x,y\\}=\\{x,y\\}$. Then $Q$ contains a subpath
$x^{\prime},x,y,y^{\prime}$, where $x^{\prime}\in X$ and $y^{\prime}\in Y$.
But by our assumption $d_{G}(x^{\prime},y^{\prime})\leq 2$, a contradiction
with the assumption that $Q$ is a shortest path. We conclude that $u$ and $v$
are $\\{x,y\\}$-positionable and consequently $\\{x,y\\}$ is a dual general
position set. $\square$

A result parallel to Theorem 3.9 for two nonadjacent vertices is simpler and
reads as follows.

###### Proposition 3.10

Let $x$ and $y$ be two non-adjacent vertices of a graph $G$. Then the set
$\\{x,y\\}$ is a dual general position set if and only if $x$ and $y$ are
simplicial vertices.

Proof. Assume first that $\\{x,y\\}$ is a dual general position set. Then $x$
is simplicial for otherwise there exist two neighbors $u$ and $v$ of $x$ such
that $d_{G}(u,v)=2$. By our assumption, $u\neq y$ and $v\neq y$, but then $u$
and $v$ are not $\\{x,y\\}$-positionable. Analogously $y$ is simplicial. The
reverse implication follows by Corollary 3.2. $\square$

##  4 The variety in Cartesian products

To determine the general position number of Cartesian product graphs is a
difficult problem and has been already widely investigated. It took several
intermediately steps before the general position number of integer lattices
(alias Cartesian products of a finite number of paths) has been determined
[13]. Bounds on the general position number of Cartesian products of arbitrary
graphs were independently proved in [7, 22]. Special Cartesian products were
studied in [23] (products of two trees), in [11] (products of paths and
cycles), and in [11, 16] (products of two cycles).

In this section we determine the total general position number, the outer
general position number, and the dual general position number of arbitrary
Cartesian products. For this purpose, we need some additional notation and
terminology on Cartesian products. Let $G$ and $H$ be graphs and consider
$G\,\square\,H$. Given a vertex $h\in V(H)$, the subgraph of $G\,\square\,H$
induced by the set of vertices $\\{(g,h):\ g\in V(G)\\}$, is a $G$-layer and
is denoted by $G^{h}$. $H$-layers ${}^{g}H$ are defined analogously. Each
$G$-layer and each $H$-layer is isomorphic to $G$ and $H$, respectively. If
$X\subseteq V(G\,\square\,H)$, the projection $p_{G}(X)$ of $X$ to $G$ is the
set $\\{g\in V(G):\ (g,h)\in X\ {\rm for\ some}\ h\in V(H)\\}$. The projection
$p_{H}(X)$ of $X$ to $H$ is defined analogously.

For total general position sets, Corollary 2.2 implies:

###### Corollary 4.1

If $G$ and $H$ are connected graphs of order at least $2$, then ${\rm gp}_{\rm
t}(G\,\square\,H)=0$.

Proof. It is straightforward to see that $G\,\square\,H$ contains no
simplicial vertices. $\square$

For outer general position sets, the following result is useful.

###### Theorem 4.2

[21, Theorem 3] If $G$ and $H$ are connected graphs, each of order at least
$2$, then $(G\,\square\,H){}_{\rm SR}\cong G{}_{\rm SR}\times H{}_{\rm SR}$.

###### Theorem 4.3

If $G$ and $H$ are two connected graphs, each of order at least $2$, then

${\rm gp}_{\rm o}(G\,\square\,H)=\min\\{{\rm gp}_{\rm o}(G),{\rm gp}_{\rm
o}(H)\\}.$

Proof. By Theorem 2.3 we have ${\rm gp}_{\rm
o}(G\,\square\,H)=\omega((G\,\square\,H){}_{\rm SR})$. Theorem 4.2 implies
that $\omega((G\,\square\,H){}_{\rm SR})=\omega(G{}_{\rm SR}\times H{}_{\rm
SR})$. Since $\omega(G\times H)=\min\\{\omega(G),\omega(H)\\}$, see [8,
Exercise 16.1], we have ${\rm gp}_{\rm
o}(G\,\square\,H)=\min\\{\omega(G{}_{\rm SR}),\omega(H{}_{\rm SR})\\}$. Using
Theorem 2.3 again we conclude that ${\rm gp}_{\rm
o}(G\,\square\,H)=\min\\{{\rm gp}_{\rm o}(G),{\rm gp}_{\rm o}(H)\\}$.
$\square$

###### Corollary 4.4

If $m,n\geq 3$, then ${\rm gp}_{\rm o}(K_{m}\,\square\,K_{n})=\min\\{m,n\\}$.

For dual general position sets, the following result that characterizes convex
subgraphs of Cartesian product graphs will be applied.

###### Lemma 4.5

[8, Lemma 6.5] A subgraph $W$ of $G=G_{1}\,\square\,\cdots\,\square\,G_{k}$ is
convex if and only if $W=U_{1}\,\square\,\cdots\,\square\,U_{k}$, where each
$U_{i}$ is convex in $G_{i}$.

###### Theorem 4.6

Let $G$ and $H$ be two graphs, each of order at least $2$. Then ${\rm gp}_{\rm
d}(G\,\square\,H)>0$ if and only if one factor is complete and the other
factor has a simplicial vertex. Moreover,

  1. (i)

${\rm gp}_{\rm d}(K_{n}\,\square\,K_{m})=\max\\{n,m\\}$, and

  2. (ii)

if $H$ is not complete and contains a simplicial vertex, then ${\rm gp}_{\rm
d}(K_{n}\,\square\,H)=n$.

Proof. Set $V(G)=[n]$ and $V(H)=[m]$. So we have
$V(G\,\square\,H)=[n]\times[m]$.

Assume first that ${\rm gp}_{\rm d}(G\,\square\,H)>0$ and let $X$ be a dual
general position set of $G\,\square\,H$. Then $X$ is clearly a general
position set of $G\,\square\,H$ and hence by Theorem 3.1,
$K=(G\,\square\,H)-X$ is a convex subgraph of $G\,\square\,H$. Consequently,
by Lemma 4.5 we infer that $K=G^{\prime}\,\square\,H^{\prime}$, where
$G^{\prime}$ is convex in $G$ and $H^{\prime}$ is convex in $H$. Suppose that
$G^{\prime}$ and $H^{\prime}$ are proper subgraphs of $G$ and $H$,
respectively. Then there exist vertices $g\in V(G)\setminus V(G^{\prime})$ and
$h\in V(H)\setminus V(H^{\prime})$, such that $g$ has a neighbor
$g^{\prime}\in V(G)$ and $h$ has a neighbor $h^{\prime}\in V(H)$. Then
$(g^{\prime},h),(g,h),(g,h^{\prime})$ is an induced path of $G\,\square\,H$,
where all its vertices are from $X$, a contradiction.

By the above contradiction, $p_{G}(X)=V(G)$ or $p_{H}(X)=V(H)$. We may without
loss of generality assume that $p_{G}(X)=V(G)$. Since layers in Cartesian
products are convex, this implies that $V(G)$ is a general position set in $G$
which in turn implies that $G$ is a complete graph. Moreover, since $X$ is a
general position set we also see that $|p_{H}(X)|=1$ and let $h$ be the unique
vertex of $H$ to which $X$ projects. Now, if $h$ is not a simplicial vertex of
$H$, then there exist vertices $h^{\prime},h^{\prime\prime}\in N_{H}(h)$ such
that $h^{\prime}h^{\prime\prime}\notin E(H)$. But then $K$ is clearly not
convex, hence $h$ must be a simplicial vertex of $H$.

To complete the argument we observe that if $G$ is complete and $h\in V(H)$ is
a simplicial vertex, then by Theorem 3.1 the set $V(G)\times\\{h\\}$ is a dual
general position set.

The two formulas in the cases when ${\rm gp}_{\rm d}(G\,\square\,H)>0$ follow
directly from the above discussion. $\square$

In [22, Theorem 3.8] it is proved that ${\rm
gp}(K_{m}\,\square\,K_{n})=m+n-2$. Combining this result with Corollary 4.4
and Theorem 4.6 we see that the four general position invariants considered
can vary arbitrary. For instance, for any $n\geq 3$ we have:

$\displaystyle{\rm gp}(K_{n}\,\square\,K_{2n})$ $\displaystyle=3n-2,$
$\displaystyle{\rm gp}_{\rm d}(K_{n}\,\square\,K_{2n})$ $\displaystyle=2n,$
$\displaystyle{\rm gp}_{\rm o}(K_{n}\,\square\,K_{2n})$ $\displaystyle=n,$
$\displaystyle{\rm gp}_{\rm t}(K_{n}\,\square\,K_{2n})$ $\displaystyle=0.$

##  5 Concluding remarks

In this paper we have introduced the variety of general position sets. We have
completely described the total general position sets and the outer general
position sets. On the other hand, we have observed that the dual general
position sets are not hereditary. This fact makes the investigation of dual
general position sets quite tricky. For instance, we have given a sufficient
condition for a graph $G$ to satisfy ${\rm gp}_{\rm d}(G)=0$, yet we were not
been able to characterize graphs $G$ with this property. The same problems
remains open for the case ${\rm gp}_{\rm d}(G)=1$.

We have seem that if $G$ is a block graph, then ${\rm gp}(G)={\rm gp}_{\rm
o}(G)={\rm gp}_{\rm d}(G)={\rm gp}_{\rm t}(G)$. It would be an interesting
project to characterize the graphs for which this holds. Moreover, the same
question can be posed for each subsets of the involved invariants, for
instance, to characterize the graphs $G$ for which ${\rm gp}(G)={\rm gp}_{\rm
d}(G)$ holds.

## Acknowledgments

Many thanks to James Tuite, who suggested to investigate the variety of the
general position sets in parallel to the variety of mutual-visibility sets.
This work was supported by the Slovenian Research Agency ARIS (research core
funding P1-0297 and projects J1-2452, N1-0285).

## Declaration of interests

The authors declare that they have no conflict of interest.

## Data availability

Our manuscript has no associated data.

## References

  * [1]
  * [2] B.S. Anand, U. Chandran S.V., M. Changat, S. Klavžar, E.J. Thomas, Characterization of generalposition sets and its applications to cographs and bipartite graphs, Appl. Math. Comput. 359 (2019) 84–89.
  * [3] U. Chandran S.V., G.J. Parthasarathy, The geodesic irredundant sets in graphs, Int. J. Math. Combin. 4 (2016) 135–143.
  * [4] S. Cicerone, G. Di Stefano, L. Drožđek, J. Hedžet, S. Klavžar, I.G. Yero, Variety of mutual-visibility problems in graphs, Theoret. Comput. Sci. 974 (2023) Paper 114096.
  * [5] S. Cicerone, G. Di Stefano, S. Klavžar, I.G. Yero, Mutual-visibility in strong products of graphs via total mutual-visibility, arXiv:2210.07835 [math.CO].
  * [6] G. Di Stefano, Mutual visibility in graphs, Appl. Math. Comput. 419 (2022) 126850.
  * [7] M. Ghorbani, H.R. Maimani, M. Momeni, F.R. Mahid, S. Klavžar, G. Rus, The general position problem on Kneser graphs and on some graph operations, Discuss. Math. Graph Theory 41 (2021) 1199–1213.
  * [8] R. Hammack, W. Imrich, S. Klavžar, Handbook of Product Graphs, Second Edition, CRC Press, Boca Raton, FL, 2011.
  * [9] V. Iršič, S. Klavžar, G. Rus, J. Tuite, General position polynomials, arXiv:2401.05696[math.CO]; also: Results Math., to appear.
  * [10] S. Klavžar, I.G. Yero, The general position problem and strong resolving graphs, Open Math. 17 (2019) 1126–1135.
  * [11] S. Klavžar, B. Patkós, G. Rus, I.G. Yero, On general position sets in Cartesian products, Results Math. 76 (2021) Paper 123.
  * [12] S. Klavžar, D.F. Rall, I.G. Yero, General $d$-position sets, Ars Math. Contemp. 21 (2021) #P1.03.
  * [13] S. Klavžar, G. Rus, The general position number of integer lattices, Appl. Math. Comput. 390 (2021) Paper 125664.
  * [14] S. Klavžar, J. Tian, J. Tuite, Builder-Blocker general position games, arXiv:2310.19949 [math.CO].
  * [15] J. Körner, On the extremal combinatorics of the Hamming space, J. Comb. Theory Ser. A 71 (1995) 112–126.
  * [16] D. Korže, A. Vesel, General position sets in two families of Cartesian product graphs, Mediterr. J. Math. 20 (2023) Paper 203.
  * [17] D. Kuziak, M.L. Puertas, J.A. Rodríguez-Velázquez, I.G. Yero, Strong resolving graphs: the realization and the characterization problems, Discrete Appl. Math. 236 (2018) 270–287.
  * [18] P. Manuel, S. Klavžar, A general position problem in graph theory, Bull. Aust. Math. Soc. 98 (2018) 177–187.
  * [19] P. Manuel, R. Prabha, S. Klavžar, The edge general position problem, Bull. Malays. Math. Sci. Soc. 45 (2022) 2997–3009.
  * [20] O.R. Oellermann, J. Peters-Fransen, The strong metric dimension of graphs and digraphs, Discrete Appl. Math. 155 (2007) 356–364.
  * [21] J.A. Rodríguez-Velázquez, I.G. Yero, D. Kuziak, O.R. Oellermann, On the strong metric dimension of Cartesian and direct products of graphs, Discrete Math. 335 (2014) 8–19.
  * [22] J. Tian, K. Xu, The general position number of Cartesian products involving a factor with small diameter, Appl. Math. Comput. 403 (2021) Paper 126206.
  * [23] J. Tian, K. Xu, S. Klavžar, The general position number of the Cartesian product of two trees, Bull. Aust. Math. Soc. 104 (2021) 1–10.


This work was partially funded by the ANR Cadence ANR-16-CE32-0007 and Chair
“Modélisation Mathématique et Biodiversité” of VEOLIA-Ecole polytechnique-
MNHN-F.X

M.S. acknowledges the MIUR Excellence Department Project awarded to the
Department of Mathematics, University of Rome “Tor Vergata” CUP
E83C18000100006 and thanks the INdAM unit GNAMPA.

## References

  * [Andjel(1982)] E. D. Andjel.  Invariant Measures for the Zero Range Process.  _The Annals of Probability_ , 10(3):525 – 547, 1982.  doi: 10.1214/aop/1176993765.  URL https://doi.org/10.1214/aop/1176993765.
  * [Ball and Donnelly(1995)] F. Ball and P. Donnelly.  Strong approximations for epidemic models.  _Stochastic processes and their applications_ , 55(1):1–21, 1995.
  * [Bansaye and Lambert(2013)] V. Bansaye and A. Lambert.  New approaches of source-sink metapopulations decoupling the roles of demography and dispersal.  _Theoretical Population Biology_ , 88:31–46, 2013.
  * [Bansaye and Méléard(2015)] V. Bansaye and S. Méléard.  _Stochastic models for structured populations_.  Springer, 2015.
  * [Barbour and Reinert(2013)] A. Barbour and G. Reinert.  Approximating the epidemic curve.  _Electronic Journal of Probability_ , 18:1–30, 2013.
  * [Bascompte and Sole(1996)] J. Bascompte and R. V. Sole.  Habitat fragmentation and extinction thresholds in spatially explicit models.  _Journal of Animal Ecology_ , 65(4):465–473, 1996\.
  * [Berger(2002)] N. Berger.  Transience, recurrence and critical behavior for long-range percolation.  _Communications in mathematical physics_ , 226(3):531–558, 2002.
  * [Daley and Vere-Jones(2008)] D. J. Daley and D. Vere-Jones.  _An introduction to the theory of point processes. Vol. II_.  Probability and its Applications. Springer, New York, second edition, 2008\.  ISBN 978-0-387-21337-8.  doi: 10.1007/978-0-387-49835-5.  URL https://doi.org/10.1007/978-0-387-49835-5.
  * [Dalmau and Salvi(2021)] J. Dalmau and M. Salvi.  Scale-free percolation in continuous space: quenched degree and clustering coefficient.  _Journal of Applied Probability_ , 58(1):106–127, 2021.  doi: 10.1017/jpr.2020.76.
  * [Deijfen et al.(2013)Deijfen, van der Hofstad, and Hooghiemstra] M. Deijfen, R. van der Hofstad, and G. Hooghiemstra.  Scale-free percolation.  In _Annales de l’Institut Henri Poincaré, Probabilités et Statistiques_ , volume 49, pages 817–838. Institut Henri Poincaré, 2013\.
  * [Deprez and Wüthrich(2018)] P. Deprez and M. V. Wüthrich.  Scale-free percolation in continuum space.  _Communications in Mathematics and Statistics_ , Jul 2018.  ISSN 2194-671X.  doi: 10.1007/s40304-018-0142-0.  URL https://doi.org/10.1007/s40304-018-0142-0.
  * [Durrett(1995)] R. Durrett.  Ten lectures on particle systems.  _Lectures on Probability Theory_ , pages 97–201, 1995.
  * [Faggionato(2010)] A. Faggionato.  Hydrodynamic limit of zero range processes among random conductances on the supercritical percolation cluster.  _Electronic Journal of Probability_ , 15:259–291, 2010\.
  * [Faggionato(2022a)] A. Faggionato.  Stochastic homogenization of random walks on point processes.  _to appear in Annales de l’Institut Henri Poincaré_ , 2022a.
  * [Faggionato(2022b)] A. Faggionato.  Hydrodynamic limit of simple exclusion processes in symmetric random environments via duality and homogenization.  _Probability Theory and Related Fields_ , 184(3):1093–1137, 2022b.  doi: 10.1007/s00440-022-01163-8.  URL https://doi.org/10.1007/s00440-022-01163-8.
  * [Ganguly and Ramanan(2022)] A. Ganguly and K. Ramanan.  Hydrodynamic limits of non-markovian interacting particle systems on sparse graphs.  _arXiv_ , 2022.  URL https://arxiv.org/abs/2205.01587.
  * [Gonçalves and Jara(2008)] P. Gonçalves and M. Jara.  Scaling limits for gradient systems in random environment.  _Journal of Statistical Physics_ , 131(4):691–716, 2008.
  * [Hastings(1983)] A. Hastings.  Can spatial variation alone lead to selection for dispersal ?  _Theoretical Population Biology,_ , 24(3):244–251, 1983.
  * [Hiebeler(2000)] D. Hiebeler.  Populations on fragmented landscapes with spatially structured heterogeneities : landscape generation and local dispersal.  _Ecology_ , 81(6):1629–1641, 2000.
  * [Hutchcroft(2021)] T. Hutchcroft.  Power-law bounds for critical long-range percolation below the upper-critical dimension.  _Probability Theory and Related Fields_ , 181(1):533–570, 2021.
  * [Ikeda and Watanabe(1989)] N. Ikeda and S. Watanabe.  _Stochastic differential equations and diffusion processes_.  North-Holland Publishing Company, 1989.
  * [Jara and Landim(2008)] M. D. Jara and C. Landim.  Quenched non-equilibrium central limit theorem for a tagged particle in the exclusion process with bond disorder.  _Ann. Inst. Henri Poincaré Probab. Stat._ , 44(2):341–361, 2008.  ISSN 0246-0203.  doi: 10.1214/07-AIHP112.  URL https://doi.org/10.1214/07-AIHP112.
  * [Kipnis and Landim(1998)] C. Kipnis and C. Landim.  _Scaling limits of interacting particle systems_ , volume 320.  Springer Science & Business Media, 1998.
  * [Kipnis and Varadhan(1986)] C. Kipnis and S. R. S. Varadhan.  Central limit theorem for additive functionals of reversible Markov processes and applications to simple exclusions.  _Communications in Mathematical Physics_ , 104(1):1 – 19, 1986.  doi: cmp/1104114929.  URL https://doi.org/.
  * [Kurtz(1981)] T. G. Kurtz.  _Approximation of population processes_.  SIAM, 1981.
  * [Levins(1969)] R. Levins.  Some demographic and genetic consequences of environmental heterogeneity for biological control.  _Bulletin of the Entomological society of America_ , 15(3), 1969.
  * [Liggett(1973)] T. M. Liggett.  An Infinite Particle System with Zero Range Interactions.  _The Annals of Probability_ , 1(2):240 – 253, 1973.  doi: 10.1214/aop/1176996977.  URL https://doi.org/10.1214/aop/1176996977.
  * [Meleard and Roelly(1993)] S. Meleard and S. Roelly.  _Sur les convergences etroite ou vague de processus a valeurs mesures[On the vague and weak convergence of measure-valued processes]_.  Universität Bielefeld. Forschungszentrum Bielefeld-Bochum-Stochastik [BiBoS], 1993.  URL https://books.google.it/books?id=SgjvtgAACAAJ.
  * [Moller and Waagepetersen(2003)] J. Moller and R. P. Waagepetersen.  _Statistical inference and simulation for spatial point processes_.  Chapman and Hall/CRC, 2003.
  * [Montagnon(2019)] P. Montagnon.  A stochastic sir model on a graph with epidemiological and population dynamics occurring over the same time scale.  _Journal of mathematical biology_ , 79(1):31–62, 2019.
  * [Penrose(1991)] M. D. Penrose.  On a continuum percolation model.  _Advances in Applied Probability_ , 23(3):536–556, 1991.  ISSN 00018678.  URL http://www.jstor.org/stable/1427621.
  * [Perrut(2000)] A. Perrut.  Hydrodynamic limits for a two-species reaction-diffusion process.  _The Annals of Applied Probability_ , 10(1):163–191, 2000.
  * [Pulliam(1988)] H. R. Pulliam.  Sources, sinks, and population regulation.  _American naturalist_ , pages 652–661, 1988.
  * [Qi et al.(2019)Qi, Beaunée, Arnoux, Dutta, Joly, Vergu, and Ezanno] L. Qi, G. Beaunée, S. Arnoux, B. L. Dutta, A. Joly, E. Vergu, and P. Ezanno.  Neighbourhood contacts and trade movements drive the regional spread of bovine viral diarrhoea virus (bvdv).  _Veterinary Research_ , 50(1):30, 2019.  doi: 10.1186/s13567-019-0647-x.  URL https://doi.org/10.1186/s13567-019-0647-x.
  * [Vershynin(2018)] R. Vershynin.  _High-dimensional probability: An introduction with applications in data science_ , volume 47.  Cambridge university press, 2018.


# Plug-and-Play Acceleration of Occupancy Grid-based NeRF Rendering using VDB
Grid and Hierarchical Ray Traversal

Yoshio Kato, Shuhei Tarashima
NTT Communications, Japan
{yoshio.kato<EMAIL_ADDRESS>
###### Abstract

Transmittance estimators such as Occupancy Grid (OG)[10] can accelerate the
training and rendering of Neural Radiance Field (NeRF) by predicting important
samples that contributes much to the generated image. However, OG manages
occupied regions in the form of the dense binary grid, in which there are many
blocks with the same values that cause redundant examination of voxels’
emptiness in ray-tracing. In our work, we introduce two techniques to improve
the efficiency of ray-tracing in trained OG without fine-tuning. First, we
replace the dense grids with VDB[11] grids to reduce the spatial redundancy.
Second, we use hierarchical digital differential analyzer (HDDA)[12] to
efficiently trace voxels in the VDB grids. Our experiments on NeRF-
Synthetic[9] and Mip-NeRF 360[3] datasets show that our proposed method
successfully accelerates rendering NeRF-Synthetic dataset[9] by 12% in average
and Mip-NeRF 360 dataset[3] by 4% in average, compared to a fast
implementation of OG, NerfAcc[8], without losing the quality of rendered
images.

##  1 Introduction

Neural Radiance Fields (NeRFs) have shown impressive results in novel view
synthesis tasks by using neural networks and ray tracing to model volume
density and view-dependent appearance[9]. While NeRF-based methods represent
detailed geometry and photorealistic appearance, they are suffered from high
computational costs in rendering. For instance, the original NeRF method
requires days to train a single scene and 10 seconds to render a frame[9].

Usually a NeRF model can be divided into two main modules: a ray-sampler and a
radiance field. When we calculate a color of the given pixel, at first the
ray-sampler decides the sampling points on the camera ray that associates to
the pixel, and then sampled points are fed into the radiance field to predict
the density and color of each point. Finally, these values are accumulated to
the pixel color. Recently, many methods for accelerating training or rendering
have been proposed by modifying radiance fields[10, 17, 14, 5, 15, 4] or
improving ray-samplers[10, 3]. In addition, it is known that they also improve
convergence speed in training. In this work, we focus on ray-samplers to give
benefits to the trained NeRF models without large computational cost such as
fine-tuning[19]. Since improving ray-samplers and radiance fields orthogonally
contribute to rendering acceleration, our work on ray-samplers can be combined
with any Occupancy Grid (OG)[10]-based model.

The main aim of ray-samplers is to sample important points on a ray. In ray-
tracing, we can reduce the number of samples without losing the quality by
selecting points with higher densities. For example, NerfAcc[8] demonstrates
that OG can serve as a good sampling method of both faster convergence and
rendering for various NeRF methods.

Dispite its performance and usability, OG manages occupied regions in the form
of the dense binary grid and has spatial redundancy. It makes rendering slower
due to a number of unnecessary operations to search occupied voxels on a ray.
To resolve this problem, we propose a method that replace the OG-based ray-
sampler without re-training or fine-tuning. Our method is composed of two
techniques. First, to reduce spatial redundancy in OG, we use VDB[11], a data
structure for sparse volumes. This data structure merges a block of a number
of empty voxels. Second, to synergistically accelerate sampling with VDB, we
use an efficient ray-tracing algorithm called Hierarchical Digital
Differential Analyzer (HDDA)[12], which skips a merged empty voxel at one
operation. These two techniques reduce the number of operations to traverse
voxels on a ray, and accelerate the ray-sampler.

As far as we know, this work is the first paper that utilizes a hierarchical
data structure and a hierarchical ray tracing algorithm simultaneously in the
context of NeRF rendering acceleration. To evaluate our method, we trained
Instant-NGP[10] with a normal OG-based ray-sampler and replaced it with our
VDB-based algorithm before starting to render images. We used NeRF-Synthetic
dataset[9] and Mip-NeRF 360 dataset[3], and showed that in most cases our
method improved rendering FPS while preserving PSNR compared to the NerfAcc[8]
implementation. In addition, we showed using VDB and HDDA together makes much
larger improvements than using either technique in some cases. Our code is
available at https://github.com/Yosshi999/faster-occgrid.

##  2 Related Works

###  2.1 Efficient Ray-Sampler

By sampling the points which contributes much to the final rendered image,
i.e., the points with high density, we can reduce the number of samples
without losing the quality of synthesized images. Several approaches to
identify high-density points have been proposed. Occupancy Grid (OG)[10]
caches the predicted densities in NeRF output during training, and the ray
tracer samples from the voxels whose density is higher than a threshold. Mip-
NeRF 360[3] proposed Proposal Network (PN), a neural network to estimate the
density of queried points. However, since PN requires a number of network
forward inferences to suggest sampling points, it unavoidably demands
additional computational costs. Therefore, PN contributes to faster
convergence of training but is not suited to improve rendering efficiency. In
this work, we adopt OG as a baseline because we focus on the faster rendering.

###  2.2 Sparse Data Structures

Some NeRF methods create feature grids to represent a radiance field, in which
there are usually large vacuum regions. Thus, it is important to reduce the
number of accesses to such vaccum regions. This is also true for OG. To reduce
such spatial redundancy in the grid, we can adopt sparse data structures that
are widely investigated in the domain of Computer Graphics (CG). One approach
is Octree[7], which recursively subdivides the grid and represents its
containment relationship as a tree. It can reduce its spatial redundancy by
pruning the nodes which associate to the empty spaces. This enables skipping
large empty regions and accelerating ray-tracing. Instant-NGP[10] uses Octree-
like structure when it represents OG in training larger scenes, but no pruning
is performed. Another approach is VDB[11], a tree-like data structure to store
sparse voxels in a hierarchical manner. Unlike Octree, VDB fixes the depth of
its tree and saves the computational cost to traverse the tree in accessing
voxels. In addition, VDB provides a caching mechanism to accelerate accessing
neighboring voxels. Notice that PlenVDB[18] already adopts VDB for
representing the radiance field to achieve fast voxel accessing and efficient
memory usage. However, it doesn’t utilize VDB’s hierarchical structure for
ray-tracing. This fact motivated us to fully exploit VDB for OG, which is
connectable to various NeRF-based methods. In addition, we focus on more
efficient ray-tracing algorithms that could be run on VDB’s hierarchical
structure, which will be described in the next section.

###  2.3 Enumerating Line-Grid Intersections

In CG research community, efficient ray marching methods are widely
investigated. They are also useful for faster NeRF rendering. In this section,
we introduce some ray marching algorithm that suit with grid based NeRF
algorithms.

A widely adopted algorithm is DDA[2]. It efficiently enumerates the voxels
that intersect a given line. In NeRF rendering, we can sample points from
occupied voxels on a ray while skipping empty voxels. However, NeRF scenes
usually have many empty regions and skipping only one voxel for each iteration
is inefficient. There have been some approaches to efficiently skip multiple
voxels in the literature. One way is to retrieve the distance for which we can
skip safely from the current point[16, 6]. However, this requires large
additional memory to save integers in the all voxels. Another approach is a
hierarchical technique. HDDA[12] utilizes VDB’s hierarchical structure and
skips a large empty subspace. Fig. 1 visualizes three approaches: DDA[2] as a
baseline, Chessboard Distance[16] as a skipping method with distance
retrieval, and HDDA[12] as a hierarchical approach. In this work, we use HDDA
to efficiently search significant voxels in our VDB-structured OG. As far as
we know, modifing the ray-tracing algorithm to suit hierarchical data
structure is the first attempt in the domain of accelerating NeRF’s ray-
sampler.

Figure 1: Examples of ray-marching algorithms. DDA (left), Chessboard Distance
(CD)[16] (center), and HDDA on quadtree (right). Black dots depict lookup
operations. Black lines are where the colors are sampled. White voxel means
empty space. In DDA, we need lookup the voxel’s occupancy one by one. CD saves
the $L_{\infty}$ distance to the nearest occupied voxel in advance. HDDA can
skip by power of two according to the information in the quadtree.

PSNR | chair | drums | ficus | hotdog | lego | materials | mic | ship | ave.
---|---|---|---|---|---|---|---|---|---
NerfAcc | 35.74 | 25.45 | 33.96 | 37.33 | 35.79 | 29.58 | 36.71 | 30.57 | 33.14
VDB + DDA branch | 35.74 | 25.45 | 33.96 | 37.33 | 35.79 | 29.58 | 36.71 | 30.57 | 33.14
VDB + DDA skip | 35.74 | 25.45 | 33.96 | 37.33 | 35.79 | 29.58 | 36.71 | 30.57 | 33.14
VDB + HDDA branch | 35.64 | 25.43 | 33.96 | 37.33 | 35.68 | 29.57 | 36.64 | 30.55 | 33.10
VDB + HDDA skip | 35.64 | 25.43 | 33.96 | 37.33 | 35.68 | 29.57 | 36.64 | 30.55 | 33.10

FPS | chair | drums | ficus | hotdog | lego | materials | mic | ship | ave.
---|---|---|---|---|---|---|---|---|---
NerfAcc | 4.22 | 4.19 | 4.27 | 4.24 | 4.29 | 5.06 | 4.48 | 3.28 | 4.25
VDB + DDA branch | 4.67 | 4.58 | 4.63 | 4.89 | 4.77 | 5.63 | 4.86 | 3.78 | 4.73
VDB + DDA skip | 4.03 | 3.83 | 3.94 | 4.32 | 4.08 | 4.79 | 4.29 | 3.46 | 4.09
VDB + HDDA branch | 4.60 | 4.32 | 4.41 | 4.86 | 4.76 | 5.68 | 4.85 | 3.71 | 4.64
VDB + HDDA skip | 4.73 | 4.48 | 4.54 | 4.94 | 4.82 | 5.85 | 5.03 | 3.80 | 4.77

Table 1: Rendering results on NeRF-Synthetic dataset.

PSNR | outdoor | indoor |
---|---|---|---
bicycle | flowers | garden | stump | treehill | room | counter | kitchen | bonsai | ave.
NerfAcc | 22.33 | 19.98 | 24.56 | 23.17 | 22.06 | 30.52 | 26.90 | 27.92 | 29.99 | 25.27
VDB + DDA branch | 22.33 | 19.98 | 24.56 | 23.17 | 22.06 | 30.52 | 26.90 | 27.92 | 29.99 | 25.27
VDB + DDA skip | 22.34 | 19.98 | 24.56 | 23.17 | 22.06 | 30.53 | 26.90 | 27.93 | 30.00 | 25.28
VDB + HDDA branch | 22.32 | 19.98 | 24.56 | 23.17 | 22.06 | 30.5 | 26.88 | 27.91 | 29.98 | 25.26
VDB + HDDA skip | 22.32 | 19.98 | 24.56 | 23.17 | 22.06 | 30.51 | 26.88 | 27.92 | 29.99 | 25.27

FPS | outdoor | indoor |
---|---|---|---
bicycle | flowers | garden | stump | treehill | room | counter | kitchen | bonsai | ave.
NerfAcc | 1.21 | 1.64 | 1.63 | 1.17 | 1.30 | 4.37 | 4.03 | 4.61 | 4.20 | 2.69
VDB + DDA branch | 1.34 | 1.80 | 1.83 | 1.29 | 1.41 | 4.64 | 4.15 | 4.78 | 4.36 | 2.84
VDB + DDA skip | 1.25 | 1.62 | 1.69 | 1.21 | 1.27 | 4.27 | 3.63 | 4.16 | 3.80 | 2.55
VDB + HDDA branch | 1.31 | 1.78 | 1.81 | 1.27 | 1.37 | 4.53 | 4.11 | 4.74 | 4.39 | 2.81
VDB + HDDA skip | 1.31 | 1.80 | 1.82 | 1.28 | 1.39 | 4.59 | 3.96 | 4.66 | 4.46 | 2.81

Table 2: Rendering results on Mip-NeRF 360 dataset.

##  3 Method

We convert Occupancy Grid (OG)[10] of a trained NeRF model into VDB-based
structure using OpenVDB[1], and transfer it to GPU using NanoVDB[13]. In this
work, we use Instant-NGP[10] as a base model. If there are some redundancies
in the VDB grid, we prune them and manage the large occupied or unoccupied
region as a tile, where the tile contains multiple voxels sharing same values.
When the ray-sampler collects points on a ray, we use HDDA[12] to efficiently
traverse grids on the ray. Every time we find an occupied voxel or a fully
occupied tile, we sample points along the ray at specified intervals; a
constant stepsize for NeRF-Synthetic dataset[9] and a linearly increasing
stepsize for Mip-NeRF 360 dataset[3]. Usually ray-sampling is processed on GPU
and each thread is assigned to each ray. We note that there are mainly two
implementation variants for the ray-sampling kernel. One algorithm branches in
traversing a grid according to its occupancy, and the other skips all empty
cells and then marches in a grid. The former, we named it DDA branch, is
adopted by NerfAcc[8], and the latter, we named it DDA skip, is adoped by
Instant-NGP. We show the algorithms in the supplementary material Sec. 6. In
this work, we compare the rendering speed by changing the ray-sampling kernel.

For larger scenes such as Mip-NeRF 360, we prepare multi-resolution VDB grids
by following the setting of Instant-NGP[10]. When the ray-sampler accesses the
voxels and multiple voxels are intersected at the same time, it prioritises
finer voxels.

##  4 Experimental Results

###  4.1 Experimental Setup

We used NeRF-Synthetic dataset[9] for bounded scenes and Mip-NeRF 360
dataset[3] for unbounded scenes. NeRF-Synthetic contains eight synthetic
scenes and each scene has 100 images for training and 200 images for testing.
We prepared a single Occupancy Grid (OG) with resolution $128^{3}$ for NeRF-
Synthetic. Mip-NeRF 360 contains four indoor and five outdoor photorealistic
scenes and each scene has between 100 and 330. We followed the setting of
Instant-NGP[10] and prepared four multi-resolution grids and each grid has
resolution $128^{3}$ and voxel size $2^{b}$, where $b\in[0,3]$ for Mip-NeRF
360. On both datasets we trained Instant-NGP with 20k iterations and the
batchsize of 1024. We updated OG every 16 iterations in training. We used
NerfAcc[8] as a baseline and forked it to implement our VDB-based ray-sampler
and experiments. As far as we know, NerfAcc is the fastest implementation of
OG[8].

After training NeRF models, we converted the dense grids of OG into VDB[11].
It took only 60 msec to covert the dense grids in the worst case. Next, we
rendered the test images to measure FPS, PSNR, and the amount of memory
allocated by VDB grids. We selected the ray-tracing algorithm from DDA and
HDDA described in Sec. 2.3, and selected the kernel implementation from DDA
branch and DDA skip described in Sec. 3. All experiments are conducted on a
Ubuntu server with 1x NVIDIA A100 GPU.

###  4.2 Results

Tab. 1 shows that our method improves the rendering FPS in the all cases in
NeRF-Synthetic dataset. In most cases, the ray-sampler using VDB and HDDA with
the DDA skip kernel records the fastest FPS, and accelerate rendering by 12%
in average. In the best case, hotdog scene gets faster by 16% in rendering.
Note that no scene got significantly worse PSNR than the baseline.

Tab. 2 shows that in Mip-NeRF 360 dataset our method improves the rendering
FPS by 4-5% in average. Similarly to the experiment on NeRF-Synthetic dataset,
all scenes don’t get worse significantly in PSNR. We note that introducing
HDDA did not work well for Mip-NeRF 360 dataset and in most cases the ray-
sampler with DDA and the kernel DDA branch was the best. In addition, the
extent of speedup on Mip-NeRF 360 dataset is smaller than that of NeRF-
Synthetic dataset.

Tab. 3 shows that the memory usage of VDB grids is about twice larger than the
baseline, which uses a bitarray representing dense boolean grids. In
particular, VDB grids converted from Occupancy Grid trained on Mip-NeRF 360
dataset are tend to be much larger because of the VDB’s overhead. However, we
believe it is acceptable because additional memory usage is at most 1.5MiB,
since the size of a family of compact NeRF-based models is around 5MiB[5].

| Size (KiB)
---|---
chair | 336.5
drums | 410.4
ficus | 388.6
hotdog | 337.5
lego | 339.9
materials | 327.4
mic | 316.1
ship | 363.1
ave. | 352.4

| Size (KiB)
---|---
bicycle | 2259.0
flowers | 2145.4
garden | 2089.7
stump | 2157.9
treehill | 2279.8
room | 1999.1
counter | 2116.8
kitchen | 2155.8
bonsai | 2105.8
ave. | 2145.5

Table 3: The size of VDB grids converted from Occupancy Grid (OG) trained on
NeRF-Synthetic dataset (left) and Mip-NeRF 360 dataset (right). Before
conversion, OG trained on NeRF-Synthetic is 256KiB and OG trained on Mip-NeRF
360 is 1024KiB.

##  5 Discussion

In this study we proposed to use a VDB-based Occupancy Grid (OG) and a
sampling algorithm using HDDA to accelerate NeRF rendering. Our experiments
showed that it improves rendering speed, without losing the quality of
rendered images. We emphasize that our method can be adopted for the trained
NeRF models whose ray-sampler is based on OG. However, for larger scenes such
as Mip-NeRF 360[3], our improvement tends to be marginal, possibly because of
an overhead in processing multiple VDB grids. It is necessary to compare the
amount of additional memory consumption and FPS improvement when our method is
adopted in production. In addition, when we replaced the ray-sampler with
ours, it was not able to generate the entirely same images as the original
ray-sampler generates. One potential reason lies in floating errors that could
negatively affects the rendering results.

We also find that DDA skip, skipping leading empty cells in advance, did not
work well with DDA, as shown in ”VDB + DDA skip” rows of Tab. 1 and Tab. 2.
However, by using VDB together with HDDA, the rendering speed got faster than
the baseline. While we believe this is because HDDA could reduce the number of
operations for skipping voxels and saved the computational time in all
threads, deeper investigations of the CUDA performances should be performed in
the future work.

It is notable that using other sparse data structure such as Octree is also
worth investigating. While VDB restricts the depth of tree and requires larger
sub-grids for each level, the dimension of sub-grid is always $2^{3}$ in
Octree and its fineness may help the effectiveness of representing sparse
scenes. In addition, Octree-based OG may be more memory-efficient because the
structure of Octree is simpler than VDB.

A possible extension of our work is to accelerate training. One of the
difficulties of adopting efficient data structure in training is to minimize
the overhead of optimizing spatial redundancy. Since pruning requires
computation time to some extent, we can’t frequently prune the variables that
is intermittently updated during training. Our proposed method is not suitable
for frequent updates because the VDB grid located on GPU is read-only and we
have to re-transfer the grid pruned on CPU to GPU. An efficient backend with
low-cost pruning is worth investigating.

## References

  * [1] OpenVDB.  https://www.openvdb.org/.
  * Amanatides and Woo [1987] John Amanatides and Andrew Woo.  A Fast Voxel Traversal Algorithm for Ray Tracing.  _Proceedings of EuroGraphics_ , 87, 1987.
  * Barron et al. [2022] Jonathan T. Barron, Ben Mildenhall, Dor Verbin, Pratul P. Srinivasan, and Peter Hedman.  Mip-NeRF 360: Unbounded Anti-Aliased Neural Radiance Fields.  _CVPR_ , 2022.
  * Cao and Johnson [2023] Ang Cao and Justin Johnson.  HexPlane: A Fast Representation for Dynamic Scenes.  _CVPR_ , 2023.
  * Chen et al. [2022] Anpei Chen, Zexiang Xu, Andreas Geiger, Jingyi Yu, and Hao Su.  TensoRF: Tensorial Radiance Fields.  In _European Conference on Computer Vision (ECCV)_ , 2022.
  * Es and İşler [2007] Alphan Es and Veysi İşler.  Accelerated regular grid traversals using extended anisotropic chessboard distance fields on a parallel stream processor.  _Journal of Parallel and Distributed Computing_ , 67(11):1201–1217, 2007.
  * Knoll [2006] Aaron Knoll.  A Survey of Octree Volume Rendering Methods.  In _Visualization of Large and Unstructured Data Sets_ , 2006.
  * Li et al. [2023] Ruilong Li, Hang Gao, Matthew Tancik, and Angjoo Kanazawa.  NerfAcc: Efficient Sampling Accelerates NeRFs.  _arXiv preprint arXiv:2305.04966_ , 2023.
  * Mildenhall et al. [2020] Ben Mildenhall, Pratul P. Srinivasan, Matthew Tancik, Jonathan T. Barron, Ravi Ramamoorthi, and Ren Ng.  NeRF: Representing Scenes as Neural Radiance Fields for View Synthesis.  In _ECCV_ , 2020.
  * Müller et al. [2022] Thomas Müller, Alex Evans, Christoph Schied, and Alexander Keller.  Instant Neural Graphics Primitives with a Multiresolution Hash Encoding.  _ACM Trans. Graph._ , 41(4):102:1–102:15, 2022.
  * Museth [2013] Ken Museth.  VDB: High-resolution sparse volumes with dynamic topology.  _ACM Trans. Graph._ , 32(3), 2013.
  * Museth [2014] Ken Museth.  Hierarchical digital differential analyzer for efficient ray-marching in OpenVDB.  In _ACM SIGGRAPH 2014 Talks_ , New York, NY, USA, 2014. Association for Computing Machinery.
  * Museth [2021] Ken Museth.  NanoVDB: A GPU-Friendly and Portable VDB Data Structure For Real-Time Rendering And Simulation.  In _ACM SIGGRAPH 2021 Talks_ , New York, NY, USA, 2021. Association for Computing Machinery.
  * Sara Fridovich-Keil and Alex Yu et al. [2022] Sara Fridovich-Keil and Alex Yu, Matthew Tancik, Qinhong Chen, Benjamin Recht, and Angjoo Kanazawa.  Plenoxels: Radiance Fields without Neural Networks.  In _CVPR_ , 2022.
  * Sara Fridovich-Keil and Giacomo Meanti et al. [2023] Sara Fridovich-Keil and Giacomo Meanti, Frederik Rahbæk Warburg, Benjamin Recht, and Angjoo Kanazawa.  K-Planes: Explicit Radiance Fields in Space, Time, and Appearance.  In _CVPR_ , 2023.
  * Sramek and Kaufman [2000] Milos Sramek and Arie Kaufman.  Fast ray-tracing of rectilinear volume data using distance transforms.  _Visualization and Computer Graphics, IEEE Transactions on_ , 6:236 – 252, 2000.
  * Sun et al. [2022] Cheng Sun, Min Sun, and Hwann-Tzong Chen.  Direct Voxel Grid Optimization: Super-fast Convergence for Radiance Fields Reconstruction.  In _CVPR_ , 2022.
  * Yan et al. [2023] Han Yan, Celong Liu, Chao Ma, and Xing Mei.  PlenVDB: Memory Efficient VDB-Based Radiance Fields for Fast Training and Rendering .  In _CVPR_ , 2023.
  * Yu et al. [2021] Alex Yu, Ruilong Li, Matthew Tancik, Hao Li, Ren Ng, and Angjoo Kanazawa.  PlenOctrees for Real-time Rendering of Neural Radiance Fields.  In _ICCV_ , 2021.

Supplementary Material

##  6 Variants of Ray-Sampling Kernel

Algorithm 1 Algorithm of DDA branch. Analyzer returns index $ijk$ of the next
voxel intersected by the ray($o,d$), and interval of $t\in[t_{0},t_{1}]$ where
$o+td$ is inside the voxel. grid.at returns whether the voxel at $ijk$ is
occupied or not.

1:function dda_branch($ray,t_{\min},t_{\max}$)

2: $buf\leftarrow[\ ]$

3: $t_{last}\leftarrow t_{\min}$

4: while $t_{last}\leq t_{\max}$ do

5: // Analyzer is DDA or HDDA.

6: $ijk,t_{0},t_{1}\leftarrow\mathrm{Analyzer(}ray,t_{last}\mathrm{)}$

7: while $t_{last}\leq t_{0}$ do

8: $t_{last}\leftarrow t_{last}+\Delta t$

9: end while

10: while $t_{last}\leq t_{1}$ do

11: if grid.at($ijk$) then // Grid is dense or VDB.

12: $buf.append(t_{last})$

13: end if

14: $t_{last}\leftarrow t_{last}+\Delta t$

15: end while

16: end while

17: return $buf$

18:end function

Algorithm 2 Algorithm of DDA skip.

1:function dda_skip($ray,t_{\min},t_{\max}$)

2: $buf\leftarrow[\ ]$

3: $t_{last}\leftarrow t_{\min}$

4: while $t_{last}\leq t_{\max}$ do

5: $t_{1}\leftarrow t_{\min}$

6: repeat

7: $ijk,t_{0},t_{1}\leftarrow\mathrm{Analyzer(}ray,t_{1}\mathrm{)}$

8: until !grid.at($ijk$)

9: while $t_{last}\leq t_{0}$ do

10: $t_{last}\leftarrow t_{last}+\Delta t$

11: end while

12: while $t_{last}\leq t_{1}$ do

13: $buf.append(t_{last})$

14: $t_{last}\leftarrow t_{last}+\Delta t$

15: end while

16: end while

17: return $buf$

18:end function

We show the ray-sampling algorithms tested by our work in Algorithm 1 and
Algorithm 2. As we describe in Sec. 3, DDA branch (Algorithm 1) synchronizes
the voxel traversal on all workers, and branches according to each voxel’s
occupancy. On the other hand, DDA skip (Algorithm 2) skips all leading empty
voxels and then marches in the occupied voxel. DDA in the both algorithms can
be replaced with HDDA.