Springe direkt zu Inhalt

Othman Watad:

Experimental Evaluation of an Algorithm for Finding a Triangle in Disc Graphs


Given a set S of n discs, where the center coordinates of each disc D ⊂ R^2 and each disc has an associated radius RD > 0. The disc graph is the graph with the set S and an edge between two discs A and B if and only if the euclidean distance between A and B |AB| is smaller or equal to the sum of the radii RA and RB, i.e., if the two discs directly intersect.

The problem of finding triangles in disc graphs has been studied by Kaplan et al. in the research paper "Finding Triangles and Computing the Girth in Disk Graphs". This problem is particularly difficult for general graphs, but specific graph classes, such as planar graphs do already have a solution.

Kaplan et al. observe that a triangle within a disc graph can be found in 𝒪(n log n) worst- case time. In this thesis, an attempt has been made to implement their theoretical approach in a real- world setting.

Bachelor of Science (B.Sc.)