Potentials and limitations of visual methods for the exploration of complex data structures ; Möglichkeiten und Grenzen visueller Methoden für die Exploration komplexer Datenstrukturen
You can manage bookmarks using lists, please log in to your user account for this.
Media type:
Doctoral Thesis;
Electronic Thesis;
E-Book
Title:
Potentials and limitations of visual methods for the exploration of complex data structures ; Möglichkeiten und Grenzen visueller Methoden für die Exploration komplexer Datenstrukturen
Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
Visualizations can be used for the analysis of algorithms and data structures as well as for algorithm teaching and learning. If interactive animations or simulations are available, learners can explore the data structures and algorithms on their own. By seeing how an algorithm reacts to different input sets, a deeper understanding and hence, better learning, is expected. Similarly, visualization can be a helpful research tool for the analysis of complex data structures and the algorithms operating on them. For a formal mathematical analysis, the right approach to the problem is often the most decisive step. A suitable visual representation of the structure and the dynamics of the involved algorithms can provide important clues for the initial idea. Using the example of a relatively recent data structure, the priority search pennant, we show how visualizations can support the analysis of algorithms for complex geometric range queries on sets of point in the two-dimensional plane. Priority search pennants are similar to the better-known priority search trees; the structure is interesting since the rigid heap order known from many implementations of priority queues is weakened. As a result, priority search pennants are easier to maintain than priority search trees when the set of points is dynamic, i.e. when points are inserted and deleted and the underlying tree has to be rebalanced. This advantage comes at a cost: certain range queries have been shown to have a higher asymptotic complexity for priority search pennants than for priority search trees. However, it has been unclear whether this is also true for other frequently occurring types of range queries. We analyze the complexity of those operations which, for a given rectangular query range, return the leftmost, rightmost, or bottommost point of the set, respectively. It is shown that these operations enjoy the same asymptotic bounds in priority search pennants as they do in priority search trees. In addition, a sharp upper and lower bound for the actual ...