Efficient Algorithms for Constructing a Pyramid from a Terrain*This paper was presented at Japan Conference on Discrete and Computation Geometry 2002 (JCDCG 2002).

In [5], the following pyramid construction problem was proposed: Given nonnegative valued functions ρ and μ in d variables, we consider the optimal pyramid maximizing the total parametric gain of ρ against μ. The pyramid can be considered as the optimal unimodal approximation of ρ relative to μ, and can be applied to hierarchical data segmentation. In this paper, we give efficient algorithms for a couple of two-dimensional pyramid construction problems.