Two quadtree algorithms are presented that use table driven traversals to reduce the time complexity required to achieve their respective goals. The first algorithm is a two step process that converts a boundary representation of a polygon into a corresponding region representation of the same image. The first step orders the border pixels of the polygon. The second step fills in the polygon in O(B) time where B is the number of border pixels for the polygon of interest. A table propagates the correct values of upcoming nodes in a simulated traversal of the final region quadtree. This is unique because the pointer representation of the tree being traversed does not exist. A linear quadtree representation is constructed as this traversal proceeds. The second algorithm is an update algorithm for a quadtree (or octtree) of moving particles. Particle simulations have had the long-standing problem of calculating the interactions among n particles. It takes O(n2) time for direct computation of all the interactions between n particles. Greengard [Gree87, Carr87] has devised a way to approximate these calculations in linear time using a tree data structure. However, the particle simulation must still rebuild the particle tree after every iteration, which requires O(n log n) time. Our algorithm updates the existing tree of particles, rather than building a new tree. It operates in near linear time in the number of particles being simulated. The update algorithm uses a table to store particles as they move between nodes of the tree. / Master of Science

Thesis (MSc)--Stellenbosch University, 2013. / ENGLISH ABSTRACT: The main objective of our study is enumerating spanning trees (G) and perfect matchings PM(G) on graphs G and lattices L. We demonstrate two methods of enumerating spanning trees of any connected graph, namely the matrix-tree theorem and as a special value of the Tutte polynomial T(G; x; y). We present a general method for counting spanning trees on lattices in d 2 dimensions. In particular we apply this method on the following regular lattices with d = 2: rectangular, triangular, honeycomb, kagomé, diced, 9 3 lattice and its dual lattice to derive a explicit formulas for the number of spanning trees of these lattices of finite sizes. Regarding the problem of enumerating of perfect matchings, we prove Cayley’s theorem which relates the Pfaffian of a skew symmetric matrix to its determinant. Using this and defining the Pfaffian orientation on a planar graph, we derive explicit formula for the number of perfect matchings on the following planar lattices; rectangular, honeycomb and triangular. For each of these lattices, we also determine the bulk limit or thermodynamic limit, which is a natural measure of the rate of growth of the number of spanning trees (L) and the number of perfect matchings PM(L). An algorithm is implemented in the computer algebra system SAGE to count the number of spanning trees as well as the number of perfect matchings of the lattices studied. / AFRIKAANSE OPSOMMING: Die hoofdoel van ons studie is die aftelling van spanbome (G) en volkome afparings PM(G) in grafieke G en roosters L. Ons beskou twee metodes om spanbome in ’n samehangende grafiek af te tel, naamlik deur middel van die matriks-boom-stelling, en as ’n spesiale waarde van die Tutte polinoom T(G; x; y). Ons behandel ’n algemene metode om spanbome in roosters in d 2 dimensies af te tel. In die besonder pas ons hierdie metode toe op die volgende reguliere roosters met d = 2: reghoekig, driehoekig, heuningkoek, kagomé, blokkies, 9 3 rooster en sy duale rooster. Ons bepaal eksplisiete formules vir die aantal spanbome in hierdie roosters van eindige grootte. Wat die aftelling van volkome afparings aanbetref, gee ons ’n bewys van Cayley se stelling wat die Pfaffiaan van ’n skeefsimmetriese matriks met sy determinant verbind. Met behulp van hierdie stelling en Pfaffiaanse oriënterings van planare grafieke bepaal ons eksplisiete formules vir die aantal volkome afparings in die volgende planare roosters: reghoekig, driehoekig, heuningkoek. Vir elk van hierdie roosters word ook die “grootmaat limiet” (of termodinamiese limiet) bepaal, wat ’n natuurlike maat vir die groeitempo van die aantaal spanbome (L) en die aantal volkome afparings PM(L) voorstel. ’n Algoritme is in die rekenaaralgebra-stelsel SAGE geimplementeer om die aantal spanboome asook die aantal volkome afparings in die toepaslike roosters af te tel.

Thesis (MSc)--Stellenbosch University, 2014. / ENGLISH ABSTRACT: A greedy tree is constructed from a given degree sequence using a simple greedy algorithm that assigns the highest degree to the root, the second, the third, . . . , -highest degree to the root’s neighbours, etc. This particular tree is the solution to numerous extremal problems among all trees with given degree sequence. In this thesis, we collect results for some distancebased graph invariants, the number of subtrees and the spectral radius in which greedy trees play a major role. We show that greedy trees are extremal for the aforementioned graph invariants by means of two different approaches, one using level greedy trees and majorization, while the other one is somewhat more direct. Finally, we prove some new results on greedy trees for additive parameters with specific toll functions. / AFRIKAANSE OPSOMMING: ’n Gulsige boom word vanuit ’n gegewe graadry deur middel van ’n eenvoudige gulsige algoritme gebou, wat die hoogste graad aan die wortel toewys, die tweede-, derde-, . . . , -hoogste graad aan die wortel se bure, ens. Hierdie spesifieke boom is die oplossing van ’n groot aantal ekstremale probleme onder al die bome met gegewe graadry. In hierdie tesis beskou ons ’n versameling van resultate oor afstand-gebaseerde grafiekinvariante, die aantal subbome en die spektraalstraal waarin gulsige bome ’n belangrike rol speel. Ons bewys dat gulsige bome ekstremaal vir die bogenoemde grafiekinvariante is deur van twee verskillende tegnieke gebruik te maak: een met behulp van vlak-gulsige bome en majorering, en ’n ander metode wat effens meer direk is. Laastens bewys ons sommige nuwe resultate oor gulsige bome vir additiewe parameters met spesifieke tolfunksies.

Thesis (MComm) -- Stellenbosch University, 2002. / ENGLISH ABSTRACT: Consider a data set with a categorical response variable and a set of explanatory variables. The response variable can have two or more categories and the explanatory variables can be numerical or categorical. This is a typical setup for a classification analysis, where we want to model the response based on the explanatory variables. Traditional statistical methods have been developed under certain assumptions such as: the explanatory variables are numeric only and! or the data follow a multivariate normal distribution. hl practice such assumptions are not always met. Different research fields generate data that have a mixed structure (categorical and numeric) and researchers are often interested using all these data in the analysis. hl recent years robust methods such as classification trees have become the substitute for traditional statistical methods when the above assumptions are violated. Classification trees are not only an effective classification method, but offer many other advantages. The aim of this thesis is to highlight the advantages of classification trees. hl the chapters that follow, the theory of and further developments on classification trees are discussed. This forms the foundation for the CART software which is discussed in Chapter 5, as well as other software in which classification tree modeling is possible. We will compare classification trees to parametric-, kernel- and k-nearest-neighbour discriminant analyses. A neural network is also compared to classification trees and finally we draw some conclusions on classification trees and its comparisons with other methods. / AFRIKAANSE OPSOMMING: Beskou 'n datastel met 'n kategoriese respons veranderlike en 'n stel verklarende veranderlikes. Die respons veranderlike kan twee of meer kategorieë hê en die verklarende veranderlikes kan numeries of kategories wees. Hierdie is 'n tipiese opset vir 'n klassifikasie analise, waar ons die respons wil modelleer deur gebruik te maak van die verklarende veranderlikes. Tradisionele statistiese metodes is ontwikkelonder sekere aannames soos: die verklarende veranderlikes is slegs numeries en! of dat die data 'n meerveranderlike normaal verdeling het. In die praktyk word daar nie altyd voldoen aan hierdie aannames nie. Verskillende navorsingsvelde genereer data wat 'n gemengde struktuur het (kategories en numeries) en navorsers wil soms al hierdie data gebruik in die analise. In die afgelope jare het robuuste metodes soos klassifikasie bome die alternatief geword vir tradisionele statistiese metodes as daar nie aan bogenoemde aannames voldoen word nie. Klassifikasie bome is nie net 'n effektiewe klassifikasie metode nie, maar bied baie meer voordele. Die doel van hierdie werkstuk is om die voordele van klassifikasie bome uit te wys. In die hoofstukke wat volg word die teorie en verdere ontwikkelinge van klassifikasie bome bespreek. Hierdie vorm die fondament vir die CART sagteware wat bespreek word in Hoofstuk 5, asook ander sagteware waarin klassifikasie boom modelering moontlik is. Ons sal klassifikasie bome vergelyk met parametriese-, "kernel"- en "k-nearest-neighbour" diskriminant analise. 'n Neurale netwerk word ook vergelyk met klassifikasie bome en ten slote word daar gevolgtrekkings gemaak oor klassifikasie bome en hoe dit vergelyk met ander metodes.

Thesis (PhD)--Stellenbosch University, 2015. / ENGLISH ABSTRACT : In this thesis, a number of combinatorial objects are enumerated. Du and Yin as well as Shin and Zeng (by a different approach) proved an elegant formula for the number of labelled trees with respect to a given in degree sequence, where each edge is oriented from a vertex of lower label towards a vertex of higher label. We refine their result to also take the number of sources (vertices of in degree 0) or sinks (vertices of out degree 0) into account. We find formulas for the mean and variance of the number of sinks or sources in these trees. We also obtain a differential equation and a functional equation satisfied by the generating function for these trees. Analogous results for labelled trees with two marked vertices, related to functional digraphs, are also established. We extend the work to count reachable vertices, sinks and leaf sinks in these trees. Among other results, we obtain a counting formula for the number of labelled trees on n vertices in which exactly k vertices are reachable from a given vertex v and also the average number of vertices that are reachable from a specified vertex in labelled trees of order n. In this dissertation, we also enumerate certain families of set partitions and related tree-like structures. We provide a proof for a formula that counts connected cycle-free families of k set partitions of {1, . . . , n} satisfying a certain coherence condition and then establish a bijection between these families and the set of labelled free k-ary cacti with a given vertex-degree distribution. We then show that the formula also counts coloured Husimi graphs in which there are no blocks of the same colour that are incident to one another. We extend the work to count coloured oriented cacti and coloured cacti. Noncrossing trees and related tree-like structures are also considered in this thesis. Specifically, we establish formulas for locally oriented noncrossing trees with a given number of sources and sinks, and also with given indegree and outdegree sequences. The work is extended to obtain the average number of reachable vertices in these trees. We then generalise the concept of noncrossing trees to find formulas for the number of noncrossing Husimi graphs, cacti and oriented cacti. The study is further extended to find formulas for the number of bicoloured noncrossing Husimi graphs and the number of noncrossing connected cycle-free pairs of set partitions. / AFRIKAANSE OPSOMMING : In hierdie tesis word ’n aantal kombinatoriese objekte geenumereer. Du en Yin asook Shin en Zeng (deur middel van ’n ander benadering) het ’n elegante formule vir die aantal geëtiketteerde bome met betrekking tot ’n gegewe ingangsgraadry, waar elke lyn van die nodus met die kleiner etiket na die nodus met die groter etiket toe georiënteer word. Ons verfyn hul resultaat deur ook die aantal bronne (nodusse met ingangsgraad 0) en putte (nodusse met uitgangsgraad 0) in ag te neem. Ons vind formules vir die gemiddelde en variansie van die aantal putte of bronne in hierdie bome. Ons bepaal verder ’n differensiaalvergelyking en ’n funksionaalvergelyking wat deur die voortbringende funksie van hierdie bome bevredig word. Analoë resultate vir geëtiketteerde bome met twee gemerkte nodusse (wat verwant is aan funksionele digrafieke), is ook gevind. Ons gaan verder voort deur ook bereikbare nodusse, bronne en putte in hierdie bome at te tel. Onder andere verkry ons ’n formule vir die aantal geëtiketteerde bome met n nodusse waarin presies k nodusse vanaf ’n gegewe nodus v bereikbaar is asook die gemiddelde aantal nodusse wat bereikbaar is vanaf ’n gegewe nodus. Ons enumereer in hierdie tesis verder sekere families van versamelingsverdelings en soortgelyke boom-vormige strukture. Ons gee ’n bewys vir ’n formule wat die aantal van samehangende siklus-vrye families van k versamelingsverdelings op {1, . . . , n} wat ’n sekere koherensie-vereiste bevredig, en ons beskryf ’n bijeksie tussen hierdie familie en die versameling van geëtiketteerde vrye k-êre kaktusse met ’n gegewe nodus-graad-verdeling. Ons toon ook dat hierdie formule ook gekleurde Husimi-grafieke tel waar blokke van dieselfde kleur nie insident met mekaar mag wees nie. Ons tel verder ook gekleurde georiënteerde kaktusse en gekleurde kaktusse. Nie-kruisende bome en soortgelyke boom-vormige strukture word in hierdie tesis ook beskou. On bepaal spesifiek formules vir lokaal georiënteerde nie-kruisende bome wat ’n gegewe aantal bronne en putte het asook nie-kruisende bome met gegewe ingangs- en uitgangsgraadrye. Ons gaan voort deur die gemiddelde aantal bereikbare nodusse in hierdie bome te bepaal. Ons veralgemeen dan die konsep van nie-kruisende bome en vind formules vir die aantal nie-kruisende Husimi-grafieke, kaktusse en georiënteerde kaktusse. Laastens vind ons ’n formule vir die aantaal tweegekleurde nie-kruisende Husimi-grafieke en die aantal nie-kruisende samehangende siklus-vrye pare van versamelingsverdelings.

Thesis (Ph.D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1979. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING. / Bibliography: p. 212-214. / by Robert Hunter Halstead, Jr. / Ph.D.

Rectilinear Steiner minimum tree (RSMT) problem asks for a shortest tree spanning a set of given terminals using only horizontal and vertical lines. Construction of RSMTs is an important problem in VLSI physical design. It is useful for both the detailed and global routing steps, and it is important for congestion, wire length and timing estimations during the floorplanning or placement step. The original RSMT problem assumes no obstacle in the routing region. However, in today’s designs, there can be many routing blockages, like macro cells, IP blocks and pre-routed nets. Therefore, the RSMT problem with blockages has become an important problem in practice and has received a lot of research attentions in the recent years. The RSMT problem has been shown to be NP-complete, and the introduction of obstacles has made this problem even more complicated. / In the first part of this thesis, we propose an exact algorithm, called ObSteiner, for the construction of obstacle-avoiding RSMT (OARSMT) in the presence of complex rectilinear obstacles. Our work is developed based on the GeoSteiner approach in which full Steiner trees (FSTs) are first constructed and then combined into a RSMT. We modify and extend the algorithm to allow rectilinear obstacles in the routing region. We prove that by adding virtual terminals to each routing obstacle, the FSTs in the presence of obstacles will follow some very simple structures. A two-phase approach is then developed for the construction of OARSMTs. In the first phase, we generate a set of FSTs. In the second phase, the FSTs generated in the first phase are used to construct an OARSMT. Experimental results show that ObSteiner is able to handle problems with hundreds of terminals in the presence of up to two thousand obstacles, generating an optimal solution in a reasonable amount of time. / In the second part of this thesis, we propose the OARSMT problem with slew constraints over obstacles. In modern VLSI designs, obstacles usually block a fraction of metal layers only making it possible to route over the obstacles. However, since buffers cannot be place on top of any obstacle, we should avoid routing long wires over obstacles. Therefore, we impose the slew constraints for the interconnects that are routed over obstacles. To deal with this problem, we analyze the optimal solutions and prove that the internal trees with signal direction over an obstacle will follow some simple structures. Based on this observation, we propose an exact algorithm, called ObSteiner with slew constraints, that is able to find an optimal solution in the extended Hanan grid. Experimental results show that the proposed algorithm is able to reduce nearly 5% routing resources on average in comparison with the OARSMT algorithm and is also very much faster. / Huang, Tao. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2013. / Includes bibliographical references (leaves [137]-144). / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- The rectilinear Steiner minimum tree problem --- p.1 / Chapter 1.2 --- Applications --- p.3 / Chapter 1.3 --- Obstacle consideration --- p.5 / Chapter 1.4 --- Thesis outline --- p.6 / Chapter 1.5 --- Thesis contributions --- p.8 / Chapter 2 --- Background --- p.11 / Chapter 2.1 --- RSMT algorithms --- p.11 / Chapter 2.1.1 --- Heuristics --- p.11 / Chapter 2.1.2 --- Exact algorithms --- p.20 / Chapter 2.2 --- OARSMT algorithms --- p.30 / Chapter 2.2.1 --- Heuristics --- p.30 / Chapter 2.2.2 --- Exact algorithms --- p.33 / Chapter 3 --- ObSteiner - an exact OARSMT algorithm --- p.37 / Chapter 3.1 --- Introduction --- p.38 / Chapter 3.2 --- Preliminaries --- p.39 / Chapter 3.2.1 --- OARSMT problem formulation --- p.39 / Chapter 3.2.2 --- An exact RSMT algorithm --- p.40 / Chapter 3.3 --- OARSMT decomposition --- p.42 / Chapter 3.3.1 --- Full Steiner trees among complex obstacles --- p.42 / Chapter 3.3.2 --- More Theoretical results --- p.59 / Chapter 3.4 --- OARSMT construction --- p.62 / Chapter 3.4.1 --- FST generation --- p.62 / Chapter 3.4.2 --- Pruning of FSTs --- p.66 / Chapter 3.4.3 --- FST concatenation --- p.71 / Chapter 3.5 --- Incremental construction --- p.82 / Chapter 3.6 --- Experiments --- p.83 / Chapter 4 --- ObSteiner with slew constraints --- p.97 / Chapter 4.1 --- Introduction --- p.97 / Chapter 4.2 --- Problem Formulation --- p.100 / Chapter 4.3 --- Overview of our approach --- p.103 / Chapter 4.4 --- Internal tree structures in an optimal solution --- p.103 / Chapter 4.5 --- Algorithm --- p.126 / Chapter 4.5.1 --- EFST and SCIFST generation --- p.127 / Chapter 4.5.2 --- Concatenation --- p.129 / Chapter 4.5.3 --- Incremental construction --- p.131 / Chapter 4.6 --- Experiments --- p.131 / Chapter 5 --- Conclusion --- p.135 / Bibliography --- p.137

by Cheung King Lum Kingly. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1997. / Includes bibliographical references (leaves 108-110). / Abstract --- p.ii / Acknowledgement --- p.iii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivation --- p.1 / Chapter 1.2 --- Problems in Content-Based Indexing --- p.2 / Chapter 1.3 --- Contributions --- p.3 / Chapter 1.4 --- Thesis Organization --- p.4 / Chapter 2 --- Content-Based Indexing Structures --- p.5 / Chapter 2.1 --- R-Tree --- p.6 / Chapter 2.2 --- R+-Tree --- p.8 / Chapter 2.3 --- R*-Tree --- p.11 / Chapter 3 --- Searching in Both R-Tree and R*-Tree --- p.15 / Chapter 3.1 --- Exact Search --- p.15 / Chapter 3.2 --- Nearest Neighbor Search --- p.19 / Chapter 3.2.1 --- Definition of Searching Metrics --- p.19 / Chapter 3.2.2 --- Pruning Heuristics --- p.21 / Chapter 3.2.3 --- Nearest Neighbor Search Algorithm --- p.24 / Chapter 3.2.4 --- Generalization to N-Nearest Neighbor Search --- p.25 / Chapter 4 --- An Improved Nearest Neighbor Search Algorithm for R-Tree --- p.29 / Chapter 4.1 --- Introduction --- p.29 / Chapter 4.2 --- New Pruning Heuristics --- p.31 / Chapter 4.3 --- An Improved Nearest Neighbor Search Algorithm --- p.34 / Chapter 4.4 --- Replacing Heuristics --- p.36 / Chapter 4.5 --- N-Nearest Neighbor Search --- p.41 / Chapter 4.6 --- Performance Evaluation --- p.45 / Chapter 5 --- Overlapping Nodes in R-Tree and R*-Tree --- p.53 / Chapter 5.1 --- Overlapping Nodes --- p.54 / Chapter 5.2 --- Problem Induced By Overlapping Nodes --- p.57 / Chapter 5.2.1 --- Backtracking --- p.57 / Chapter 5.2.2 --- Inefficient Exact Search --- p.57 / Chapter 5.2.3 --- Inefficient Nearest Neighbor Search --- p.60 / Chapter 6 --- Redundancy On R-Tree --- p.64 / Chapter 6.1 --- Motivation --- p.64 / Chapter 6.2 --- Adding Redundancy on Index Tree --- p.65 / Chapter 6.3 --- R-Tree with Redundancy --- p.66 / Chapter 6.3.1 --- Previous Models of R-Tree with Redundancy --- p.66 / Chapter 6.3.2 --- Redundant R-Tree --- p.70 / Chapter 6.3.3 --- Level List --- p.71 / Chapter 6.3.4 --- Inserting Redundancy to R-Tree --- p.72 / Chapter 6.3.5 --- Properties of Redundant R-Tree --- p.77 / Chapter 7 --- Searching in Redundant R-Tree --- p.82 / Chapter 7.1 --- Exact Search --- p.82 / Chapter 7.2 --- Nearest Neighbor Search --- p.86 / Chapter 7.3 --- Avoidance of Multiple Accesses --- p.89 / Chapter 8 --- Experiment --- p.90 / Chapter 8.1 --- Experimental Setup --- p.90 / Chapter 8.2 --- Exact Search --- p.91 / Chapter 8.2.1 --- Clustered Data --- p.91 / Chapter 8.2.2 --- Real Data --- p.93 / Chapter 8.3 --- Nearest Neighbor Search --- p.95 / Chapter 8.3.1 --- Clustered Data --- p.95 / Chapter 8.3.2 --- Uniform Data --- p.98 / Chapter 8.3.3 --- Real Data --- p.100 / Chapter 8.4 --- Discussion --- p.102 / Chapter 9 --- Conclusions and Future Research --- p.105 / Chapter 9.1 --- Conclusions --- p.105 / Chapter 9.2 --- Future Research --- p.106 / Bibliography --- p.108

Thesis (M.S.)--Kent State University, 2009. / Title from PDF t.p. (viewed Jan. 25, 2010). Advisor: Feodor Dragan. Keywords: greedy routing. Includes bibliographical references (p. 76-77).

Solving NP-hard facility location problems in wireless network planning is a common scenario. In our research, we study the Covering problem, a well known facility location problem with applications in wireless network deployment. We focus on networks with a sparse structure. First, we analyzed two heuristics of building Tree Decomposition based on vertex separator and perfect elimination order. We extended the vertex separator heuristic to improve its time performance. Second, we propose a dynamic programming algorithm based on the Tree Decomposition to solve the Covering problem optimally on the network. We developed several heuristic techniques to speed up the algorithm. Experiment results show that one variant of the dynamic programming algorithm surpasses the performance of the state of the art mathematical optimization commercial software on several occasions. / ix, 89 leaves : ill. ; 29 cm