DISCRETE MATHEMATICAL TECHNIQUES IN THE ANALYSIS AND ADJUSTMENT
OF HYBRID NETWORKS
I.Colomina
Institut Cartogràfic de Catalunya
Spain
ABSTRACT:
Over the past decade, adjustment of hybrid networks —usually referred to as combined adjustment within
the photogrammetric comunity— have deserved the attention of numerous researchers. In the software, when
dealing with the heterogeneous data of hybrid networks, everything tends to be more complex. The paper
shows how discrete techniques can help deal with this complexity. Two examples are discussed: the detection
of a family of gross errors and the numbering of unknowns for fill-in reduction. The concept of discrete models
for the network and standardized discrete kernels for the software are proposed.
KEY WORDS: discrete models, discrete techniques, graphs, matroids, graph filtering, hybrid networks.
1 INTRODUCTION
Over the past decade, hybrid networks have deserved
the attention of numerous researchers. This is wit-
nessed by the one time period 1984-1988 of WG
III/1 (Working Group III/1: Accuracy Aspects of
Combined Point Determination) of the ISPRS, the
two time periods 1983-1987, 1987-1991 of SSG 1.73
(Special Study Group 1.73: Integrated Geodesy) of
the IAG, and by the meetings organized, either sep-
arately or jointly, by the two organizations. Today,
integrated geodesy and combined point determina-
tion are still active research fields [5]. (The trend
towards combined approaches in geodesy and pho-
togrammetry has been mainly influenced by three fac-
tors: the advent of satellite geodesy —in particular
the Global Positioning System—, the development of
comprehensive models inciuding all type of data, and
the availability of high-speed large-capacity comput-
ers [9].)
In general, combined solutions are expected to pro-
vide more accurate and reliable results. Not less im-
portant is that global approaches lead to a cost re-
duction in software development, maintenance and
acquisition; that they promote closer collaboration
and understanding between groups traditionally in-
volved —as well as traditionally separated— in point
determination tasks; and that, as a result, they in-
troduce factors of rationality and coherence in the
corresponding point determination projects.
The combined adjustment philosophy, however, has
found small acceptance in practice.
In conventional adjustment problems, in the first
step, the unknowns and their accuracy are deter-
mined. In the second step, it is common to detect
poorly measured data subsets which can impair the
quality of the global adjustment. When dealing with
heterogeneous data sets everything tends to be more
complex and even the first step may not be easy to
614
carry out. Thus, for day-to-day practical projects, the
magnitude and structure of system equations which
result from the above general approaches may be
brought up as an argument against their application.
Indeed, this is not the point if a suitable numbering
for the unknowns is computed.
The heyday of research and development in num-
bering of graphs associated to geodetic networks was
the decade of the seventies and the early eighties. In
addition to the availability of the obtained results,!
the increasing computer capacity has contributed to
some decay of the topic.
In combined networks, however, there are patho-
logical structures which perturbate the regularity and
locality that classical photogrammetric and geodetic
networks have exhibited so far (Section 5). In order
to apply the old good algorithms, those structures
must be understood and characterized so they can be
detected and eliminated. For that purpose, discrete
mathematics seem to be the best tool.
Discrete techniques can also contribute to the
structural analysis of networks, hybrid or not (see
the related work in [7, 14]). These techniques, have
already been [implicitely| used for the generation of
initial approximations in the nonlinear cases and, in
a much lesser extent, for the detection of what is
known as gross errors. For instance, many times
l'Three statements describe the situation well.
First, the rigorous solution of the problem is NP-complete.
Secondly, there are many algorithms which perform well —
even at best— under certain regularity conditions. Last, the
problem has been somewhat closed since it has been proven
that problems not satisfying those regularity conditions are
not amenable to sparse gaussian elimination.
In what photogrammmetric and geodetic netwroks is con-
cerned, the pure numbering policy —that is, abstract time
and space complexity considerations— can be summarized as
follows: if the network is medium-sized (up to 2000—3000 un-
known groups or even less) use a sequential numbering algo-
rithm, otherwise use nested dissection; and, of course, try to
take advantage of any regular pattern which might occur (for
instance in photogrammetric blocks).
0 N MS Q N e+
q
ti
