Accelerated Least Squares Network Adjustments and Graph Decompositions

Land surveyors generally use archaic data management procedures with very little automation. One of the issues preventing development of more automated data management systems is the integration of the land survey data, as the standard method does not scale well. In this project we explore possibilities for an accelerated method of data integration for use in a land survey data management system. We begin this project by reviewing the standard method, least squares adjustment, and several variants each of which is purported to be faster than the standard method. We apply asymptotic analysis to each of these methods and compare them to determine which method should be considered further. The Helmert Blocking method is selected for further consideration as it has the lowest time complexity of the methods considered, although this time complexity depends on properties of the block structure used. This block structure is a decomposition of the network and we find that there is a gap in the research regarding the construction of this block structure. In the second phase of this project, we review graph decompositions and find a cut decomposition which nearly meets the requirement of the Helmert Blocking method. We elaborate on the cut decomposition to create a block decomposition which is more suitable for the Helmert Blocking method. We also present an exponential time recursive separator algorithm which constructs a block decomposition and an incrementally constructed data structure, the RS-Tree, that uses our algorithm to maintain a block decomposition as edges are inserted. In the third phase of this project, we present another incrementally constructed data structure, the HB-Tree, that maintains a block decomposition as simple graphs are inserted. The HB-Tree does not use any exponential time algorithms but produces a less optimal block decomposition than the RS-Tree. In the final phase of this project, we implement the HB-Tree data structure and the Helmert Blocking method and compare our system against the fastest comparable software, DynAdjust. The results of this comparison indicate that our method is more suitable for use in a land survey data management system, but less suitable for adjusting geodetic networks.

Name thesis:degree_name

Doctor of Philosophy (Ph.D.)

Level thesis:degree_level

Doctoral

Discipline thesis:degree_discipline

Computer Science

Grantor dc:publisher

Carleton University

Year dc:date.issued

2025

Author dc:creator

• Bremner, Michael Terence

Statement dc:rights

• Copyright © 2025 the author(s). Theses may be used for non-commercial research, educational, or related academic purposes only. Such uses include personal study, distribution to students, research and scholarship. Theses may only be shared by linking to the Carleton University Institutional Repository and no part may be copied without proper attribution to the author; no part may be used for commercial purposes directly or indirectly via a for-profit platform; no adaptation or derivative works are permitted without consent from the copyright owner.

Language dc:language.iso

en

DOI

10.22215/etd/2025-16785

OAI identifier oai:identifier

oai:carleton.scholaris.ca:20.500.14718/44812