A note on binary plane partitions

ABSTRACT

This paper considers {\sl binary space partition}s (BSP for short) for $n$ disjoint line segments in the plane. The BSP for a disjoint set of objects is a scheme dividing the space recursively by hyperplanes until the resulting fragments of objects are separated. The size of a BSP is the number of resulting fragments of the objects. We show that the minimal size of a BSP for $n$ disjoint line segments in the plane is $\Omega (n \log n / \log \log n)$ in the worst case. The best known upper bound due to Paterson and Yao is $O(n \log n)$.

REFERENCES

• 1: Pankaj K. Agarwal , Edward F. Grove , T. M. Murali , Jeffrey Scott Vitter, Binary Space Partitions for Fat Rectangles, SIAM Journal on Computing, v.29 n.5, p.1422-1448, March 2000 [doi>10.1137/S0097539797320578]
• 2: Mark de Berg , Marko de Groot , Mark Overmars, New results on binary space partitions in the plane, Computational Geometry: Theory and Applications, v.8 n.6, p.317-333, Nov. 1997 [doi>10.1016/S0925-7721(97)00008-4]
• 3: Mark de Berg , Marko M. de Groot , Mark H. Overmars, Perfect binary space partitions, Computational Geometry: Theory and Applications, v.7 n.1-2, p.81-91, Jan. 1997 [doi>10.1016/0925-7721(95)00045-3]
• 4: Henry Fuchs , Zvi M. Kedem , Bruce F. Naylor, On visible surface generation by a priori tree structures, Proceedings of the 7th annual conference on Computer graphics and interactive techniques, p.124-133, July 14-18, 1980, Seattle, Washington, United States
• 5: Henry Fuchs , Zvi M. Kedem , Bruce Naylor, Predetermining visibility priority in 3-D scenes (Preliminary Report), Proceedings of the 6th annual conference on Computer graphics and interactive techniques, p.175-181, August 08-10, 1979, Chicago, Illinois, United States
• 6: Michael S. Paterson , F. Frances Yao, Optimal binary space partitions for orthogonal objects, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.100-106, January 22-24, 1990, San Francisco, California, United States
• 7: M. S. Paterson , F. F. Yao, Binary partitions with applications to hidden surface removal and solid modelling, Proceedings of the fifth annual symposium on Computational geometry, p.23-32, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73836]
• 8: Michael S. Paterson , F. Frances Yao, Optimal binary space partitions for orthogonal objects, Journal of Algorithms, v.13 n.1, p.99-113, March 1992 [doi>10.1016/0196-6774(92)90007-Y]
• 9: R. A. Schumacker, R. Brand, M. Gilliland, and W. Sharp. Study for applying computer-generated images to visual simulation. Technical report AFHRL-TR-69-14, US Air Force Human Resources Laboratory, Brooks Air Force Base, San Antonio (USA), 1969.
• 10: Ivan E. Sutherland , Robert F. Sproull , Robert A. Schumacker, A Characterization of Ten Hidden-Surface Algorithms, ACM Computing Surveys (CSUR), v.6 n.1, p.1-55, March 1974 [doi>10.1145/356625.356626]

INDEX TERMS

Primary Classification:
  E. Data

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Theory, Verification

Keywords:
binary space partition, line segments