Loading...
Please wait, while we are loading the content...
Similar Documents
Algorithms for floodlight illumination and pattern matching problems (1998).
| Content Provider | CiteSeerX |
|---|---|
| Researcher | Yugandhar, V. Saxena, Sanjeev |
| Abstract | In this thesis we study a variation of the classical art gallery problem, a tree traversal technique and some combinatorial pattern matching problems. The art gallery problem studied is: Find an optimal pair of vertices on the given convex polygon and illuminating powers(wattage) of the light sources, minimizing the maximum power of the pair of light sources to be used so that each point inside the polygon is illuminated with a certain prespecified minimum intensity. Our algorithm for this problem runs in O(ffn 3 ) time. Where n is the number of vertices of the polygon and ff is the number of iterations a numerical method have to perform to obtain a desired accuracy. A general tree traversal technique is presented which improves the space complexity of a wide variety of problems. Algorithms for the following combinatorial pattern matching problems are presented: (i) Construct optimal(minimum) depth separating tree of a separable permutation. (ii) Find the number of matches of a s... |
| File Format | |
| Publisher Date | 1998-01-01 |
| Access Restriction | Open |
| Subject Keyword | Floodlight Illumination Pattern Matching Problem Light Source General Tree Traversal Technique Maximum Power Numerical Method Wide Variety Separable Permutation Classical Art Gallery Problem Certain Prespecified Minimum Intensity Tree Traversal Technique Convex Polygon Optimal Pair Desired Accuracy Following Combinatorial Pattern Art Gallery Problem Space Complexity Combinatorial Pattern |
| Content Type | Text |
| Resource Type | Thesis |
