SIAM Journal on Discrete Mathematics · 1991 · 51 citations · 0 references
ComputingComputer ScienceMathematicsAlgorithmsComputational GeometryApproximation AlgorithmsComputational ComplexityMatrix ComputationComputational Geometry FoundationsForbidden PatternsLower BoundsSparse Linear AlgebraSparse Matrix AlgorithmsSparse Matrix Computation
The problem of estimating the number of 1’s in a square 0-1 matrix with certain forbidden configurations is considered, and nearly tight bounds are provided. This is motivated by a problem in computational geometry.