ICS 266, Spring 1996, Homework Set 2

Due Tuesday, April 30, in class

Lifting transformation.
A quadratic spline is the curve formed by the set of planar points (x=f(t),y=g(t)) where f and g are both quadratic polynomials. Describe how to use the lifting transformation to transform questions about points and splines to higher-dimensional questions about points and hyperplanes. What dimension space does this transformation produce? What is the function lifting a given point (x,y) into this space?
Range search.
An axis-aligned right triangle in the x-y plane is one in which the two shorter sides are parallel to the x and y axis. Describe a data structure for, given a point set, listing all the points inside a query axis-aligned right triangle. Describe another data structure for, given a weighted point set, finding the maximum-weight point inside a query axis-aligned right triangle. What are the query times, preprocessing times, and space complexity of your data structures?
(Hint: combine recursive orthogonal range searching with onion layers.)
Recursive decomposition.
Describe algorithms for testing whether a given point in three-dimensional space is inside a given polyedron,
- ...using the inner recursive decomposition of the polyhedron
- ...using the outer recursive decomposition of the polyhedron
Which did you find easier?