Thesis (Ph.D.)--Tufts University, 2005. / Submitted to the Dept. of Computer Science. Adviser: Diane L. Souvaine. Includes bibliographical references (leaves 154-169). Access restricted to members of the Tufts University community. Also available via the World Wide Web;

Thesis (Ph. D.)--University of Missouri-Columbia, 2001. / Typescript. Vita. Includes bibliographical references (leaf 37). Also available on the Internet.

Thesis (Ph. D.)--University of Missouri-Columbia, 2001. / Typescript. Vita. Includes bibliographical references (leaf 37). Also available on the Internet.

Thesis (M.Sc.) - Carleton University, 2001. / Includes bibliographical references (p. 71-74). Also available in electronic format on the Internet.

Thesis (Ph.D.) - Carleton University, 2002. / Includes bibliographical references (p. 133-145). Also available in electronic format on the Internet.

This thesis is concerned with developing and implementing algorithms based upon the geometry of pictures. Spherical pictures have been used in many areas of combinatorial group theory, and particularly, they have shown to be a useful method when studying the second homotopy module, 1T2, of a presentation ([3],[4],[7],[12],[41] and [64]). Computational programs that implement picture theoretical and design algorithms could advance the areas in which picture theory can be used, due to the much faster time taken to derive results than that of manual calculations. A variety of algorithms are presented. A data structure has been devised to represent spherical pictures. A method is given that verifies that a given data structure represents a picture, or set of pictures, over a group presentation. This method includes a new planarity testing algorithm, which can be performed on any graph. A computational algorithm has been implemented that determines if a given presentation defines a group extension. This work is based upon the algorithm of Baik et al. [1] which has been developed using the theory of pictures. A 3-presentation for a group G is given by < P, s >, where P is a presentation for G and s is a set of generators for 1T2. The set s can be described in a number of ways. An algorithm is given that produces a generating set of spherical pictures for 1T2 when s is given in the form of identity sequences. Conversely, if s is given in terms of spherical pictures, then the corresponding identity sequences that describe 1T2 can be determined. The above algorithms are contained in the Spherical PIcture Editor (SPICE). SPICE is a software package that enables a user to manually draw pictures over group presentations and, for these pictures, call the algorithms described above. It also contains a library of generating pictures for the non abelian groups of order at most 30. Furthermore, a method has been implemented that automatically draws a spherical picture from a corresponding identity sequence. Again, this new graph drawing technique can be performed on any arbitrary graph.

<p>The first class of problem we study deals with geometric matchings. Given a set<br />of points in the plane, we study perfect matchings of those points by straight line<br />segments so that the segments do not cross. Bottleneck matching is such a matching that minimizes the length of the longest segment. We are interested in finding a bottleneck matching of points in convex position. In the monochromatic case, where any two points are allowed to be matched, we give an O(n ²)-time algorithm for finding a bottleneck matching, improving upon previously best known algorithm of O(n ³) time complexity. We also study a bichromatic version of this problem, where each point is colored either red or blue, and only points of different color can be matched. We develop a range of tools, for dealing with bichromatic non-crossing matchings of points in convex<br />position. Combining that set of tools with a geometric analysis enable us to solve the<br />problem of finding a bottleneck matching in O(n ²) time. We also design an O(n)-time<br />algorithm for the case where the given points lie on a circle. Previously best known results were O(n 3 ) for points in convex position, and O(n log n) for points on a circle.<br />The second class of problems we study deals with dilation of geometric networks.<br />Given a polygon representing a network, and a point p in the same plane, we aim to<br />extend the network by inserting a line segment, called a feed-link, which connects<br />p to the boundary of the polygon. Once a feed link is fixed, the geometric dilation<br />of some point q on the boundary is the ratio between the length of the shortest path<br />from p to q through the extended network, and their Euclidean distance. The utility of<br />a feed-link is inversely proportional to the maximal dilation over all boundary points.<br />We give a linear time algorithm for computing the feed-link with the minimum overall<br />dilation, thus improving upon the previously known algorithm of complexity that is<br />roughly O(n log n).</p> / <p>Prva klasa problema koju proučavamo tičee se geometrijskih mečinga. Za dat skup tačaaka u ravni, posmatramo savr&scaron;ene mečinge tih tačaka spajajućii ih&nbsp; dužima koje &nbsp; se ne smeju sećui. Bottleneck mečing je takav mečing koji minimizuje dužinu najduže duži. Na&scaron; cilj je da nađemo bottleneck mečiing tačaka u konveksnom položaju.Za monohromatski slučaj, u kom je dozvoljeno upariti svaki par tačaka, dajemo algoritam vremenske složenosti O(n ²) za nalaženje bottleneck mečinga. Ovo&nbsp; je bolje od prethodno najbolji poznatog algoritam, čiija je složenost O(n ³). Takođe proučavamo bihromatsku verziju ovog problema, u kojoj je svaka tačka&nbsp; obojena ili u crveno ili u plavo, i dozvoljeno je upariti samo tačke različite boje. Razvijamo niz alata za rad sa bihromatskim nepresecajućim mečinzima tačaka u konveksnom položaju. Kombinovanje ovih alata sa geometrijskom analizom omogućava nam da re&scaron;imo problem nalaženja bottleneck mečinga u O(n ² ) vremenu. Takođe, konstrui&scaron;emo algoritam vremenske složenosti O(n) za slučaj kada&nbsp; sve date tačkke leže na krugu. Prethodno najbolji poznati algoritmi su imali složenosti&nbsp; O(n ³ ) za tačkeke u konveksnom položaju i O(n log n) za tačke na krugu.<br />Druga klasa problema koju proučaavamo tiče se dilacije u geometrijskim mrežama. Za datu mrežu predstavljenu poligonom, i tačku p u istoj ravni, želimo pro&scaron;iriti mrežu&nbsp; dodavanjem duži zvane feed-link koja povezuje p sa obodom poligona. Kada je feed- link fiksiran, defini&scaron;emo geometrijsku dilaciju neke tačke q na obodu kao odnos izme&nbsp; đu&nbsp; dužine najkraćeg puta od p do q kroz pro&scaron;irenu mrežu i njihovog Euklidskog rastojanja. Korisnost feed-linka je obrnuto proporcionalna najvećoj dilaciji od svih ta čaka na obodu poligona. Konstrui&scaron;emo algoritam linearne vremenske složenosti koji nalazi feed-link sa najmanom sveukupnom dilacijom. Ovim postižemo bolji rezultat od prethodno najboljeg poznatog algoritma složenosti približno O(n log n).</p>