Geometrische Maschinenmodelle. (Geometrical abstract automata). (German) Zbl 0642.68102

Julius-Maximilians-Universität Würzburg. 275 S. (1986).
This work is about two abstract geometrical automata: The ‘Zirkel- und Lineal-Maschine’ (ZLM) and the ‘Rechtwinkel-Lineal-Maschine’ (RLM). Both machines are structured similarly to the random access machine (RAM), but they apply geometrical instead of arithmetical operations. Hence the RAM- operations ‘\(+'\), ‘-’, ‘*’, ‘/’ are replaced by the use of compass and ruler (ZLM) or a rectangular ruler (RLM); moreover, the extended ZLM’s and RLM’s can ask geometrical queries, e.g. whether a point is in a set \(A\subseteq {\mathbb{E}}^ 2\); this corresponds to the arithmetical RAM- queries like ‘x\(\geq 0 ?'.\)
The thesis is structured as follows: After the introduction in Chapter 1 the ZLM and the RLM are presented in Chapter 2; in particular the power of the ZLM proves to be very small (Theorem 2.3.2). Therefore the extended versions A-ZLM and A-RLM are introduced in Chapter 3; these machines use a fixed oracle A, e.g. \(A\subseteq {\mathbb{E}}^ 2\) (see above). The author investigates the power of these automata basing on varying oracles A. Moreover he compares the power of different oracles, A, A’. In Chapter 4 the A-ZLM’s and A-RLM’s with indirect addressing are presented and two theorems about time-compression are proven. In Chapter 5 our geometrical automata solve a problem which is more complicated than the previous-line in O(n log n\(+K)\) time and O(n log n) space, where K is the total number of reported intersections. Our algorithms utilize set- union and set-splitting algorithms. Especially, we present a linear-time algorithm for the incremental set-splitting problem, and use it for the problem in which only insertions are allowed. The data structures developed here give new better solutions for various geometric problems on orthogonal segments. Several applications of the data structures are also discussed.


68Q45 Formal languages and automata
51M15 Geometric constructions in real or complex geometry
68Q25 Analysis of algorithms and problem complexity