This work presents the solution to two problems in Computational Geometry. First, we introduce an algorithm to calculate (provided an O( n log n) preprocessing or linear if the polygon is convex) the area of an n-gon "cut" by a query interior segment in O(n log n) time. As an application we also show how to find the line cutting 1r of the area of a convex polygon and parallel to a given line. Secondly, we show how to illuminate a stage represented by a line segment s , with floodlights placed at n points above s such that the sum of their angles is minimized. The algorithm runs in theta(n log n) time and we include a videotape presenting it.
| Identifer | oai:union.ndltd.org:uottawa.ca/oai:ruor.uottawa.ca:10393/4324 |
| Date | January 1998 |
| Creators | Contreras, Felipe. |
| Contributors | Urrutia, Jorge, |
| Publisher | University of Ottawa (Canada) |
| Source Sets | Université d’Ottawa |
| Detected Language | English |
| Type | Thesis |
| Format | 98 p. |
Page generated in 0.0021 seconds