DOI 10.1007/s00453-007-9075-9 Property-Preserving Data Reconstruction (2009)
Nir Ailon, Bernard Chazelle, Seshadhri Com, Ur Ding Liu, N. Ailon, B. Chazelle, ...
Abstract We initiate a new line of investigation into online property-preserving data reconstruction. Consider a dataset which is assumed to satisfy various (known) structural properties; e.g., it...
Geometry © 2001 Springer-Verlag New York Inc. A Trace Bound for the Hereditary Discrepancy ∗ (2008)
Abstract. Let A be the incidence matrix of a set system with m sets and n points, m ≤ n, and let t = tr M, where M = AT A. Finally, let σ = tr M 2 be the sum of squares of the elements of M. We...
Pankaj K. Agarwal, Its Relatives In, B. Chazelle, J. E. Goodman, R. Pollack, Advances In Discrete, ...
[1] P. K. Agarwal. Partitioning arrangements of lines II: Applications. Discrete & Computational
© 1996 Springer-Verlag New York Inc. Lines in Space: Combinatorics and Algorithms 1 (2008)
B. Chazelle, H. Edelsbrunner, L. J. Guibas, M. Sharir, J. Stolfi
Abstract. Questions about lines in space arise frequently as subproblems in three-dimensional computational geometry. In this paper we study a number of fundamental combinatorial and algorithmic...
The discrepancy method in computational geometry (2004)
Discrepancy theory investigates how uniform nonrandom structures can be. For example, given n points in the plane, how should we color them red and blue so as to minimize the difference between the...
New Algorithms for Near Neighbor Searching. (2002)
This paper proposes a new technique for solving near neighbor problems in the plane. We illustrate our method on the following two problems: 1. k-Nearest neighbor; Given a set S of n points in the...
Splitting a Delaunay Triangulation in Linear Time (2002)
B. Chazelle, O. Devillers, F. Hurtado, M. Mora, V. Sacristán, M. Teillaud
Computing the Delaunay triangulation of n points requires usually a minimum of #(n log n) operations, but in some special cases where some additional knowledge is provided, faster algorithms can be...
Algorithmica (1997) 17: 245–265 Decomposing the Boundary of a (1997)
Nonconvex Polyhedron, B. Chazelle, L. Palios
Abstract. We show that the boundary of a three-dimensional polyhedron with r reflex angles and arbitrary genus can be subdivided into O(r) connected pieces, each of which lies on the boundary of its...
Computational geometry and convexity / (1988)
Thesis (Ph. D.)--Yale University, 1980.
Intersection of Convex Objects in Two and Three Dimensions (1987)
One of the basic geometric operations involves determining whether a pair of convex objects intersect. This problem is well understood in a model of computation in which the objects are given as...
Computing the largest empty rectangle (1986)
B. Chazelle, R. L. Drysdalet, D. T. Lee
Abstract. We consider the following problem: Given a rectangle containingN points, find the largest area subrectangle with sides parallel to those of the original rectangle which contains none of the...
Computational geometry and convexity / (1980)
"Authorized facsimile printed by microfilm/xerography on acid-free paper ..."