\documentstyle[IEEEtran]{article}
\begin{document}
\tolerance 10000

\title{Error Estimate of the Result of Measuring Laser Beam Diameter}
\author{E. Serrano, V. P. Pytchenko, V. M. Rubinshtein, V. Kreinovich}

\pagestyle{myheadings}

\markright{APIC'95, El Paso,
Extended Abstracts,
A Supplement to the international journal of {\rm Interval
Computations}\ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ }

\maketitle

\begin{abstract}
   One of the most wide-spread methods of measuring the laser beam
diameter consists of placing a matrix of photoelements on its way,
measuring the energy (power) in each of the elements and computing
the diameter. Errors in energy measurement lead to the errors in
diameter. In the present paper we estimate the resulting error of
diameter measurements. 
\end{abstract} 
  
\auffil{The authors' addresses are: Department of Computer Science,
University of Texas at El Paso, El Paso, TX, 79968 (E.S. and V.K.);
Russia, 121433, Moscow, B. Filevskaya 41--5--35 (V.M.R.), and Russian National
Institute Electromera, St. Petersburg, Russia (V.P.P.).
This work was partially 
supported by the Soviet Science Foundation (GKNT), the
Soviet National Bureau of Standards,
NSF grant No. CDA-9015006 and NASA Research Grant No. NAG
9-757. One of the authors (V.K.) is greatly thankful
to Yuri Gurevich (University of Michigan, Ann Arbor) and Patrick
Suppes (Stanford University) for the attention to this work.}

\section{Introduction}

\subsection{Why is Knowing the Diameter of a Laser Beam so
important}
One of the characteristics of the lasers that makes them useful in many
applications is the fact that their beam is usually very thin. This
helps:
\begin{itemize}
\item in {\it communication}, when we need the signal to go only in one
direction and do not want to waste energy on the broad beams; 
\item in
{\it microsurgery} and {\it microtechnology}, where 
we need to apply the laser beam
to some small region without altering anything in the surrounding
regions, etc. 
\end{itemize}
In view of that, the diameter of the laser beam is one
of its main characteristics. 

\subsection{Definition of the Diameter}
Of course, no matter how narrow the
laser beam is, there is always some dispersion of the laser light to the
atmosphere and deviation due to the initial irregularities in its
orientation (without such dispersion we could not see the beam if
it were not oriented directly towards our eyes). However, this
dispersion is relatively small and the borders of the laser beam
are rather sharp. In other words, the main part of the energy of
the laser beam is located in some narrow region with a sharp
boundary, and so it is quite reasonable to speak about its diameter.
The natural definition of this diameter is the {\it diameter of the
circle} (orthogonal to the laser beam) {\it that contains the prevailing
part $p_0$ of the total energy of this beam}. This value $p_0$ has to be
fixed (90\% or 95\% or 99\%).
   
\subsection{How to Measure This Diameter}
 The natural way to measure this
diameter is:
\begin{itemize}
\item to place the dense matrix of photoelements in the way of the
laser beam; 
\item to measure the intensity of light of every element of this matrix;
\item to compute the total energy $I$ of the laser beam by adding these
intensities; 
\item to find a circle with the smallest radius $r$ for which 
the sum $I(r)$ of the intensities
inside this circle is greater than or equal to $p_0$ part of the total
energy (i.e., $I(r)\ge p_0\cdot I$). 
\end{itemize}

   The diameter of this circle is the desired diameter of the laser
beam. This method is widely used, and it is even accepted as a
National Standard in some countries \cite{USSR 1984}. 
   
\subsection{Measurement Errors}
Errors in this indirect process of measuring
the diameter $d$ are due to two reasons: 
\begin{itemize}
\item first, the matrix 
may not be sufficiently dense, and 
\item second, the photoelements can
measure the
intensity only with some accuracy. 
\end{itemize}
Experimental analysis
\cite{Rubinshtein 1987} has shown that if the matrix is sufficiently dense,
than the prevailing source of errors is the errors in measuring
intensity. The probabilistic distribution of these intensity
measurement errors is usually unknown, the only thing that is known
is the upper bound on this error. So if the measurement result is
$\tilde I_i$ and the error bound is $\Delta_i$, 
then the actual value of the measured
intensity can take any value from $\tilde I_i-\Delta_i$ to 
$\tilde I_i+\Delta_i$. Thus we come to the
following main problem:

\subsection{The Main Problem in Error Estimation} Given $\tilde I_i$ and
$\Delta_i$, 
how do we estimate the error in the diameter? The existing methods of
estimating this error (see, e.g., \cite{USSR 1984}) give the upper bounds
for the diameter error that are 2-3 times greater than the actual
errors \cite{Rubinshtein 1987}, so new methods are needed. 

   There exist several methods in numerical mathematics that are
aimed at solving these kind of problems: given the error estimates
of the input data of the algorithm, to give an estimate for the
output data (see, e.g., the survey volume \cite{Interval 1975}), but
these methods are mainly applicable to the case when this algorithm
implements some differentiable function, and here the
transformation from intensities to diameter is not differentiable.
So it is necessary to invent new methods. 

   In the present paper we present such a method and estimate its
computational complexity. The results were announced in 
\cite{Kreinovich et al 1988}.

\section{Mathematical Formulation of the Problem and Description of the	
Solution} 
\noindent{\it Preliminary remark.}
As we have already mentioned, in our computations, the only 
information that we need 
about the position of each element is its distance from the
center. Therefore, in order to
simplify the following denotations and computations, let's order the
elements in such a way that their distance from the center
does not decrease: the distance $r_1$ between the first element and the
center is less than or equal to the distance $r_2$ between the second
element and the center; $r_2$ is less than or equal to $r_3$ etc. So,
we arrive at the following definition.
\smallskip

\noindent{\bf Definition 1.} ({\it measurements and measured values}). 
\begin{itemize}
\item By a {\it measurement procedure},
we mean a quadruple $(N, \vec r, \vec \Delta, p_0)$, 
where $N$ is an integer, 
$\vec r=(r_1, r_2, ..., r_N)$ is a 
nondecreasing sequence of nonnegative real numbers,
$\vec \Delta=(\Delta_1, \Delta_2, ..., \Delta_N)$ 
is a sequence of positive real numbers and $p_0$ is
a real number from [0,1]. 
\begin{itemize}
\item [$\bullet$]   
The integer $N$ is called the {\it number of elements} in the matrix.
\item[$\bullet$] The
value $r_i$ is called the {\it distance} between $i-$th element and the
center, or, for short, the {\it $i$-th distance}. 
\item[$\bullet$]The value $\Delta_i$ is called the
{\it biggest possible error} of the $i$-th measurement.
\end{itemize}
\item By {\it measured intensities}, we mean a sequence of $N$ nonnegative real
numbers $\tilde I_1, \tilde I_2, ..., \tilde I_N$. The value 
$\tilde I_i$ is called {\it $i-$th measured
intensity}. 
\item By the {\it total measured intensity} $\tilde I$, we mean the sum of all
the measured intensities $\tilde I_1+\tilde I_2+...+\tilde I_N$.

\item    By the {\it measured intensity inside the radius $r$} 
(denoted by $\tilde I(r)$)
we mean the sum of all measured intensities $\tilde I_i$, for which the
corresponding distance is smaller than or equal to $r$.

\item    By the {\it measured diameter}, 
we mean the smallest value $\tilde d$, for which
$\tilde I(\tilde d/2)$ is greater than or equal to $p_0\cdot \tilde I$ 
(or, in other words, the
measured intensity inside the radius $\tilde d/2$ comprises the prevailing
part of the total measured intensity). 

\end{itemize}
\smallskip

\noindent {\bf Definition 2.} ({\it possible actual values of intensity
and possible errors})
\begin{itemize}

\item We say
that the real numbers $I_1, I_2, ..., I_N$ are {\it possible values of
intensities} iff for every $i$, 

\item[]$|\tilde I_i-I_i|\le \Delta_i$.

\item By a {\it total intensity} 
for values $I_1, I_2, ..., I_N$ we mean the sum
$I=I_1+...+I_N$.

\item By a {\it total intensity inside the radius $r$} for
the values $I_1, I_2, ..., I_N$ we mean the sum $I(r)$ 
of all the intensities $I_i$
for all $i$ such that $r_i$ is smaller than or equal to $r$. 

\item By a {\it diameter}, 
corresponding to values $I_1, I_2, ..., I_N$, we mean the
smallest value $d$, for which $I(d/2)$ is greater than or equal to
$p_0\cdot I$. 

\item We say that a real number $d$ is a {\it possible value of the
diameter},
if it is a diameter corresponding to some possible values of
intensity. 

\item By a {\it possible error in measuring diameter}, 
we mean the absolute value of the 
difference $|d-\tilde d|$ between the measured $\tilde d$ and 
a possible value of the diameter. 

\item By a {\it biggest possible error in measuring diameter}, 
we mean the greatest difference $|d-\tilde d|$ between the measured diameter
and the possible value of the diameter. This biggest possible error
will be denoted by $\Delta$. 
\end{itemize}
\smallskip

\noindent{\bf MAIN PROBLEM.} 
\begin{itemize}
\item {\it Given:} 
\begin{itemize}
\item[$\bullet$]{\sl a measurement procedure}    
\item[]$(N; r_1, r_2, ..., r_N; \Delta_1, \Delta_2, ..., \Delta_N; p_0)$
and 
\item[$\bullet$]
{\sl the measured intensities} $\tilde I_1, \tilde I_2, ..., \tilde I_N$.
\end{itemize}
\item {\it To compute:} 
{\sl the biggest
possible error $\Delta$ in measuring diameter.} 
\end{itemize}
\smallskip

\noindent{\it Comment.} The problem is not only to compute this
$\Delta$, but to try
to compute it quickly (without spending much time on computations).
The ideal situation is when the necessity to make computations (i.e.,
to process measurement results) does
not slow down the measuring devices. Thus, the running time of the ideal
processing algorithm must be of the same order as the time that is necessary 
to input the measured values. There are $N$ values, so the running
time in this ideal case must be proportional to $N$. 

To express this formally, let's recall the relevant definition.
\smallskip

\noindent {\bf Definition.} By a {\it linear-time} 
algorithm, we mean an algorithm
that finishes all the computations in time not exceeding $cN$, where
$N$ is the length of the input (in our case, the number of
measurements) and $c$ is a constant (independent on $N$).
\smallskip

\noindent {\bf THEOREM.} 
{\it There exists a linear-time algorithm for computing $\Delta$.} 

\section{Algorithm}

\begin{itemize}
 \item[1)] Preliminary steps:
   \begin{itemize}
      \item[a)] If there exist elements $i_1,...,i_k$ 
for which the distances $r_i$ are
         equal: $r_{i_1}=...=r_{i_k}$, 
then we replace each such group by a single element $i$;
to this element, we ascribe the measured intensity that is 
         equal to the sum of the correspondent
         intensities $\tilde I_i=\tilde I_{i_1}+...+\tilde I_{i_k}$, 
and the error $\Delta_i$ that is equal to the sum of the
         corresponding errors: $\Delta_i=\Delta_{i_1}+...+\Delta_{i_k}$. 
After performing this step, we have a new
         problem in which all the values $r_i$ are different.
      \item[b)] Compute $q_0=p_0/(1-p_0)$;
   \end{itemize}

 \item[2)] For $k=1, 2, ..., N$, compute the values $I^+_k$ and $I^-_k$
as follows:
\begin{itemize}
\item[$\bullet$]$I^+_1=\tilde I_1+\Delta_1$;
\item[$\bullet$]$I^+_{k+1}=I^+_k+(\tilde I_{k+1}+\Delta_{k+1})$;
\item[$\bullet$]$I^-_1=\max\{\tilde I_1-\Delta_1,0\}$;
\item[$\bullet$]$I^-_{k+1}=I^-_k+\max\{\tilde I_{k+1}-\Delta_{k+1},0\}$.
\end{itemize}
Actually, we are computing the largest and the smallest 
possible values of $I(r_i)$. 
 \item[3)] For $k=1, 2, ..., N$, compute the values 
  \begin{itemize}
    \item[$\bullet$]$q^+_k=I^+_k/(I^-_N-I^-_k)$ and 
    \item[$\bullet$]$q^-_k=I^-_k/(I^+_N-I^+_k)$.
  \end{itemize} 
When for the first time $q^+_k$ becomes greater than or equal to $q_0$, denote
the corresponding $r_k$ by $r^+$. When for the first time $q^-_k$ becomes
greater than or equal to $q_0$, denote the corresponding $r_k$ by $r^-$. 
 \item[4)] Compute $\Delta=\max\{|\tilde d-2r^+|,|\tilde d-2r^-|\}$. 
\end{itemize}

\section{Example}      
   To illustrate this algorithm, let's consider the
simplified example with 9 elements (matrix $3\times 3$) placed in a
quadratic grid; if we order them in nondecreasing order of their
distances, then we get $r_1=0, r_2=r_3=r_4=r_5=1$,
$r_6=r_7=r_8=r_9=\sqrt{2}\approx 1.41$: 
$$\matrix{6 & 3 & 7\cr 
            2  & 1 &  4\cr
            8 &   5 &   9\cr}$$
   Assume that the measured intensities are:
$$\matrix{ i &   1 &   2 &   3 &   4 &   5 &   6 &   7 &   8 &   9\cr
\tilde I_i &  10 &  6 &  7&   8 &  2&  1 &  0 &  0 &  0\cr}$$
the maximum possible error of measuring intensities is $\Delta_i=1$, and
$p_0=0.9$. 

   Let's first find the measured diameter. In this case, the total
intensity $\tilde I$ is equal to 34; $\tilde I(0)=\tilde I_1=10$ 
(smaller than $p_0\cdot 34$); $\tilde I(1)=\tilde I_1+\tilde
I_2+...+\tilde I_5=33$; this
value is already greater than $p_0\cdot 34$; so, the measured diameter
$\tilde d$ is
equal to $2\cdot 1=2$. 

   Let's now apply our algorithm to compute the maximal possible
error $\Delta $ of this value. 
\begin{itemize}
\item[1)]

\begin{itemize}
\item[a)] In this case, there exist elements with equal
distances, so according to the first step of the proposed algorithm
we must combine the elements 2 through 5 and 6 through 9 into
single elements, with measured intensities and errors equal to the
sum of the corresponding values. So we come to the new problem with
3 elements corresponding to old \#1, to old \#\# 2,...,5 and to old \#\#
6,...,9. The new intensities are correspondingly 10, 6+7+8+2=23 and
1+0+0+0=1, the errors are correspondingly 1, 1+1+1+1=4 and
1+1+1+1=4. So the new simplified problem has the following input: 
$\tilde I_1=10$, $\tilde I_2=23$, $\tilde I_3=1$, $\Delta_1=1$,
$\Delta_2=4$, $\Delta_3=4$.
\item[b)]$q_0=p_0/(1-p_0)=0.9/0.1=9$.
\end{itemize}

\item[2)] Let's compute $I^+_k$ and $I^-_k$. Following the algorithm, we
get:

\begin{itemize}
\item[$\bullet$]
  $I^+_1=10+1=11$;
\item[$\bullet$]
 $I^+_2=11+(23+4)=38$; 
\item[$\bullet$]
$I^+_3=38+(1+4)=43$;
\item[$\bullet$]
  $I^-_1=10-1=9$; 
\item[$\bullet$]
$I^-_2=9+(23-4)=28$; 
\item[$\bullet$]
$I^-_3=28+\max(1-4,0)=28+0=28$.
\end{itemize}   

\item[3)] Compute the values $q_k$: 

\begin{itemize}
\item[$\bullet$]
$q^+_1=11/(28-9)<q_0=9$;
\item[$\bullet$]
$q^-_1=9/(43-11)<9$; 
\item[$\bullet$]
$q^+_2=38/(28-28)=\infty$, which
is greater than 9; so $r^+=r_2=1$.
\item[$\bullet$]
   $q^-_2=28/(43-38)<9$; 
\item[$\bullet$]
$q^-_3=28/0=\infty> 9$ therefore, $r^-=r_3=1.41$.
\end{itemize}

\item[4)]Compute $\Delta=\max\{|2-2|, |2-2.82|\}\approx 0.82$. 
\end{itemize}

\section{The Proof}
The idea of this algorithm is very natural: the
lowest possible value of the diameter corresponds to the case when
the intensities inside this diameter take maximal possible values,
and intensities outside take lowest possible values.
Correspondingly, the lowest values outside and the biggest values
outside correspond to the case, when the estimate for the diameter
is lowest possible.

Let us use this idea to create a formal proof that our algorithm
is correct. We will prove the following four auxiliary statements:
\begin{itemize}
\item If $d$ is a possible value of a diameter, then 
\item[] $d\ge 2r^+$;
\item If $d$ is a possible value of a diameter, then 
\item[] $d\le 2r^-$;
\item $2r^+$ is a possible value of a diameter;
\item $2r^-$ is a possible value of a diameter.
\end{itemize}
Because of the third and the fourth statements, the values $|\tilde
d-2r^-|$ and $|\tilde d-2r^+|$ are the possible errors in measuring
diameter. Therefore, the maximum 
$\max\{|\tilde d-2r^+|,|\tilde d-2r^-|\}$ of these two values 
is also a possible error in
measuring diameter. Due to the first and the second statements, every
possible error in measuring diameter cannot exceed this number.
Therefore, this number is indeed equal to the desired biggest possible
error in measuring diameter. 

Let us now prove the above four statements.
\begin{itemize}
\item Let $d$ be a possible value of the diameter. This means that
$d=2r_k$, where $k$ is the first value for which $$I_1+...+I_k\ge
p_0\cdot I=p_0(I_1+...+I_N).\eqno{(1)}$$ 
The sum in the right-hand side of (1) can be represented
as sum of two terms: $$I_1+...+I_N=(I_1+...+I_k)+(I_{k+1}+...+I_N).$$
Therefore, the inequality (1) is equivalent to $$I_1+...+I_k\ge
p_0(I_1+...+I_k)+p_0(I_{k+1}+...+I_N).$$ If we move the first term in
the right-hand side to the left-hand side, we will get the equivalent
inequality $$(1-p_0)(I_1+...+I_k)\ge
p_0(I_{k+1}+...+I_N).$$ Dividing both sides of this inequality by
$1-p_0$, we conclude that $$I_1+...+I_k\ge
q_0(I_{k+1}+...+I_N)\eqno{(2)}.$$ Since $I_i$ is a possible value of $i-$th
intensity, we have $|I_i-\tilde I_i|\le\Delta_i$. Therefore, $\tilde
I_i-\Delta_i\le I_i\le \tilde I_i+\Delta_i$. Since $I_i\ge 0$, we
conclude that $I_i\ge \max(0,\tilde I_i-\Delta_i)$. So,
$$I^+_k=(\tilde I_1+\Delta_1)+...(\tilde I_k+\Delta_k)\ge
I_1+...+I_k\eqno{(3)}$$ and $$I_{k+1}+...+I_N\ge $$
$$\max(0,\tilde
I_{k+1}-\Delta_{k+1})+...+\max(0,\tilde
I_N-\Delta_N)=$$ $$I^-_N-I^-_k.\eqno{(4)}$$ From (2), (3), and (4), we
conclude that $$I^+_k\ge q_0(I^-_N-I^-_k).$$ If we divide both sides
of this inequality by $$I^-_N-I^-_k,$$ we conclude that $q^+_k\ge q_0$.
Since $r^+$ is by definition the smallest of the distances $r_i$ for 
which $q^+_i\ge q_0$,
we can conclude that $r_k\ge r_i=r^+$, i.e., that $d=2r_k\ge 2r^+$.
The first statement is proven.

\item Let us now prove the second statement. 
Let $d$ be a possible value of the diameter. We have already proved
that this means that
$d=2r_k$, where $k$ is the first (smallest) 
value for which the inequality (2)
holds. This, in turn, means that the inequality (2) is not true for
$k-1$, i.e., that: 
$$I_1+...+I_{k-1}<
q_0(I_{k}+...+I_N)\eqno{(5)}.$$ 
Since $I_i$ is a possible value of $i-$th
intensity, we have $\max(0,\tilde I_i-\Delta_i)\le I_i\le\tilde
I_i+\Delta_i$. So,
$$I^+_N - I^+_{k-1}=(\tilde I_k+\Delta_k)+...(\tilde I_N+\Delta_N)\ge$$
$$I_k+...+I_N,\eqno{(6)}$$ and $$I_{1}+...+I_{k-1}\ge $$
$$\max(0,\tilde I_{1}-\Delta_{1})+...+\max(0,\tilde
I_{k-1}-\Delta_{k-1})=$$ $$I^-_{k-1}.\eqno{(7)}$$ From (5), (6), and (7), we
conclude that $$I^-_{k-1}<q_0(I^+_N-I^+_{k-1}).$$ If we divide both sides
of this inequality by $$I^+_N-I^+_{k-1},$$ we conclude that $q^-_{k-1}<q_0$.
Since $r^-$ is by definition the smallest of the distances $r_i$ for 
which $q^-_i\ge q_0$,
we can conclude that $i>k-1$. Hence, $i\ge k$, and 
$r_{k}\le r_i=r^-$, i.e., that $d=2r_k\le 2r^-$.
The second statement is proven.

\item To prove the third statement, let us take the value $k$ for
which $r^+=r_k$, and take $I_i=\max(0,\tilde I_i-\Delta_i)$ for $i\le
k$ and $I_i=\tilde I_i+\Delta_i$ for $i>k$. Then, arguments like the
ones used in the proof of the first statement show that for this $k$, the
inequality (1) is equivalent to $q^+_k\ge q_0$. Since by definition of
$r^+$, $k$ is the first integer for which this is true, we can thus
conclude that the equivalent inequality (1) is also true. This, in its
turn, means that the actual diameter $d$, defined as $2r_i$ for the
first $i$ for which (1) is true, is $\le 2r_k=2r^+$. So, in this case,
$d\le d^+$. On the other hand,
we have already proven that in all cases (in particular, in this one),
$d\ge d^+$. This means that
in this case, $d=2r^+$.

\item The fourth statement is proved similarly, if we take as $k$, the
value for which $r^-=r_k$, and take $I_i=\tilde I_i+\Delta_i$ for
$i\le k$, and $I_i=\max(0,\tilde I_i-\Delta_i)$ otherwise.
\end{itemize}
All four statements are proven. This completes the proof of our
result. 

\begin{thebibliography}{99}
\bibitem{Interval 1975}
   {\bf Interval Mathematics}, Lecture Notes in Computer Science, Vol.
29, Springer-Verlag, Berlin-Heidelberg-New York, 1975. 
   
\bibitem{Kreinovich et al 1985}
V. Ya. Kreinovich, M. I. Pavlovich, ``Error estimate of
the result of indirect measurements by using a calculational
experiment,'' {\it Measurement Techniques}, 1985, Vol. 28, No. 3, 
pp. 201--205.

\bibitem{Kreinovich et al 1988}
V. Ya. Kreinovich, V. P. Pytchenko, V. M. Rubinshtein,
``A method for estimating the error of the laser beam
diameter measurement'', {\it Proc. 7-th National Conference on Photometry
and its Metrological Support}, Moscow, National Research Institute
of Optical and Physical Measurements, 1988, p. 46 (in Russian).
   
\bibitem{Rubinshtein 1987}
V. M. Rubinshtein, ``Error estimates for measuring space-energy 
parameters of laser beam'', In: {\bf Metrological support of
spatio-energetic measurements of laser beams}, Moscow, National
Research Institute of Physical, Technical and Radio Measurements,
1987, pp. 31--47 (in Russian).
   
\bibitem{USSR 1984}
{\bf USSR State Standard (GOST) 26.086-84. Lasers. Methods of
measuring the beam diameter and the energy spread of the
laser beam}, USSR National Bureau of Standards, Moscow, 1984 
(in Russian).
    
\end{thebibliography}
\end{document}