Klee, Paul, 1879-1940, Swiss painter, graphic artist, and art theorist, b. near Bern. Klee's enormous production (more than 10,000 paintings, drawings, and etchings) is unique in that it represents the successful combination of his sophisticated theories of art with a very personal inventiveness that has the appearance of great innocence. The son of a music teacher, Klee himself was a violinist, and musical analogies permeate his writing and his approach to art. He traveled through Europe, open to many artistic influences. The most important of these were the works of Blake, Beardsley, Goya, Ensor, and, especially, Cézanne. In 1911 he became associated with the Blaue Reiter group and later exhibited as one of the Blue Four. Klee's awakening to color occurred on a trip to Tunis in 1914, a year after he had met Delaunay and been made aware of new theories of color use. Thereafter his whimsical and fantastic images were rendered with a luminous and subtle color sense.

Klee's works are neither abstract nor figurative, but have strong elements of both approaches. Characteristic of his gently witty paintings are The Twittering Machine (1922, Mus. of Modern Art, New York City) and Fish Magic (1925, Phila. Mus. of Art). Other works reveal strong, rhythmic patterns, as in the unsettling Viaducts Break Ranks (1937, Hamburg). World famous by 1929, Klee taught at the Bauhaus (1920-31) and at the Düsseldorf academy (1931-33) until the Nazis, who judged his work degenerate, forced him to resign. He and his family fled Germany for his native city in 1933. In his series of Pedagogical Sketchbooks (tr. 1944) and lecture notes entitled The Thinking Eye (tr. 1961), Klee sought to define his intuitive approach to artistic creation. His last ten years were spent in Switzerland, and some 4,000 of his works are in the Paul Klee Center, Bern.

See his notebooks, ed. by J. Spiller (2 vol., tr. 1992); his diaries, ed. by his son Felix Klee (tr. 1964); his life and work in documents, ed. by F. Klee (tr. 1962); studies by J. M. Joran (1984), C. Lanchner, ed. (1987), O. K. Werckmeister (1989), and M. Franciscono (1991).

In computational geometry, Klee's measure problem is the problem of determining how efficiently the measure of a union of (multidimensional) rectangular ranges can be computed. Here, a d-dimensional rectangular range is defined to be a cartesian product of d intervals of real numbers, which is a subset of Rd.

The problem is named after Victor Klee, who gave an algorithm for computing the length of a union of intervals (the case d = 1) which was later shown to be optimally efficient in the sense of computational complexity theory. The computational complexity of computing the area of a union of 2-dimensional rectangular ranges is now also known, but the case d ≥ 3 remains an open problem.

History and algorithms

In 1977, Victor Klee considered the following problem: given a collection of n intervals in the real line, compute the length of their union. He then presented an algorithm to solve this problem with computational complexity (or "running time") O(n log n) — see Big O notation for the meaning of this statement. This algorithm, based on sorting the intervals, was later shown by Michael Fredman and Bruce Weide (1978) to be optimal.

Later in 1977, Jon Bentley considered a 2-dimensional analogue of this problem: given a collection of n rectangles, find the area of their union. He also obtained a complexity O(n log n) algorithm, now known as Bentley's algorithm, based on reducing the problem to n 1-dimensional problems: this is done by sweeping a vertical line across the area. Using this method, the area of the union can be computed without explicitly constructing the union itself. Bentley's algorithm is now also known to be optimal (in the 2-dimensional case), and is used in computer graphics, among other areas.

These two problems are the 1- and 2-dimensional cases of a more general question: given a collection of n d-dimensional rectangular ranges, compute the measure of their union. This general problem is Klee's measure problem.

When generalized to the d-dimensional case, Bentley's algorithm has a running time of O(n^{d-1} log n). This turns out not to be optimal, because it only decomposes the d-dimensional problem into n (d-1)-dimensional problems, and does not further decompose those subproblems. In 1981, Jan van Leeuwen and Derek Wood improved the running time of this algorithm to O(n^{d-1}) for d ≥ 3 by using dynamic quadtrees.

In 1988, Mark Overmars and Chee Yap proposed an O(n^{d/2} log n) algorithm for d ≥ 3 which is the fastest known algorithm to date. Their algorithm uses a particular data structure similar to a kd-tree to decompose the problem into 2-dimensional components and aggregate those components efficiently; the 2-dimensional problems themselves are solved efficiently using a trellis structure. Although asymptotically faster than Bentley's algorithm, its data structures use significantly more space, so it is only used in problems where either n or d is large. In 1998, Bogdan Chlebus proposed a simpler algorithm with the same asymptotic running time for the common special cases where d is 3 or 4.

Current status

The only known lower bound for any d is Omega(n log n). The Overmars–Yap algorithm provides an upper bound of O(n^{d/2} log n), so for d ≥ 3, it remains an open question whether faster algorithms are possible, or alternatively whether tighter lower bounds can be proven. In particular, it remains open whether the algorithm's running time must depend on d. In addition, the question of whether there are faster algorithms that can deal with special cases (for example, when there is a bound on the scale of the ranges) remains open.

References and further reading

Important papers

  • Victor Klee (1977). Can the measure of cup[a_i, b_i] be computed in less than O(n log n) steps? American Mathematical Monthly 84: 284-285.
  • Jon L. Bentley (1977). Algorithms for Klee's rectangle problems. Unpublished notes, Computer Science Department, Carnegie Mellon University.
  • Michael L. Fredman and Bruce Weide (1978). The complexity of computing the measure of cup[a_i, b_i]. Communications of the ACM 21: 540-544.
  • Jan van Leeuwen and Derick Wood (1981). The measure problem for rectangular ranges in d-space. Journal of Algorithms 2: 282-300.
  • Mark H. Overmars and Chee-Keng Yap (1988). New upper bounds in Klee's measure problem. Extended abstract. Rijksuniversiteit Utrecht Technical Report RUU-CS-88-22. Full version published in SIAM Journal of Computing 20(6): 1034-1045 (1991). (PDF of the tech report version)
  • Bogdan S. Chlebus (1998). On the Klee's measure problem in small dimensions. In Proceedings of the 25th Conference on Current Trends in Theory and Practice of Informatics (SOFSEM-98) (Jasná, Slovakia, November 21-27, 1998). Also published in Springer Lecture Notes in Computer Science 1521 (Springer-Verlag, Berlin, 1998).

Secondary literature

Search another word or see Kleeon Dictionary | Thesaurus |Spanish
Copyright © 2015, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature