Joint separation of clusters : theory and experiments | |
| Author | Pattarawit PolpinitPolpinit |
| Call Number | AIT Thesis no.CS-03-32 |
| Subject(s) | Cluster set theory Polyhedra |
| Note | A thesis submitted in partial fulfillment of the requirements for the degree of Master of Science, School of Advanced Technologies |
| Publisher | Asian Institute of Technology |
| Series Statement | Thesis ; no. CS-03-32 |
| Abstract | In this study we investigate a measure of the so-called joint separation of clusters from both the experimental and the theoretical points of view. In the experimental part, we measure the joint separation of a finite set of planes F of cardinality n ¸ 2 in term of the minmax angle of vectors on the planes belonging to a given set. Minmax angle is defined as the largest angle µ such that, if n vectors are chosen, one each on the plane, then at least two of the vectors have an angle of at least µ between them. Since obtaining minmax angle for arbitrary finite sets of plane in R3 seems hard, we restrict to planes bounding the faces of a regular polyhedron. An algorithm based on Hill Climbing and Lingo model is used in the search for minmax angle of regular polyhedron. In the theoretical part, we study the generation of minmax angle as a notion of joint separation. Given a set of points of various colors on the line, an interval is called color-spanning if it contains at least one point of each color. We present an efficient algorithm to solve a problem of finding the minimum color spanning interval. Furthermore a semi-dynamic and a fully- dynamic algorithm to maintain such interval are proposed |
| Year | 2003 |
| Corresponding Series Added Entry | Asian Institute of Technology. Thesis ; no. CS-03-32 |
| Type | Thesis |
| School | School of Advanced Technologies (SAT) |
| Department | Department of Information and Communications Technologies (DICT) |
| Academic Program/FoS | Computer Science (CS) |
| Chairperson(s) | Guha, Sumanta; |
| Examination Committee(s) | Phan Minh Dung;Haddawy, Peter; |
| Scholarship Donor(s) | Development and Promotion for Science and Technology talents project of Thailand; |
| Degree | Thesis (M.Eng.) - Asian Institute of Technology, 2003 |