A vertex-face assignment for plane graphs (2008)
Diane Souvaine, Csaba D. T'oth
Abstract For any planar straight line graph (Pslg), there is a vertexface assignment such that every vertex is assigned to at most two adjacent faces, and every face is assigned to all its reflex...
Tóth, Pointed and colored binary encompassing trees (2008)
Michael Hoffmann, Csaba D. T'oth
Abstract For n disjoint line segments in the plane we construct in optimal O(n log n) time an en-compassing tree of maximum degree three such that at every vertex all incident edges lie in a...
with 2-Edge Connected Dual Graphs (2008)
Mashhood Ishaque, Diane L. Souvainek, Csaba D. T'oth
Abstract The empty space around n disjoint line segments in theplane can be partitioned into n + 1 convex faces by ex-tending the segments in some order. The dual graph of such a partition is the...
Pointed binary encompassing trees: simple and optimal (2008)
Michael Hoffmann, Csaba D. T'oth
Abstract For n disjoint line segments in the plane we con-struct in optimal O(n log n) time an encompassingtree of maximal degree three such that every vertex is pointed. Moreover, at every segment...
with 2-Edge Connected Dual Graphs (2008)
Mashhood Ishaque, Diane L. Souvainek, Csaba D. T'oth
Abstract The empty space around n disjoint line segments in theplane can be partitioned into n + 1 convex faces by ex-tending the segments in some order. The dual graph of such a partition is the...
Distinct triangle areas in a planar point set (2007)
Adrian Dumitrescu, Csaba D. T'oth
Abstract Erd""os, Purdy, and Straus conjectured that the number of distinct (nonzero) areas of the trianglesdetermined by n noncollinear points in the plane is at least b n-12 c,...
On the number of tetrahedra with minimum,unit, and distinct volumes in three-space* (2007)
Adrian Dumitrescu, Csaba D. T'oth
Abstract We formulate and give partial answers to several combinatorial problems on volumes of simplicesdetermined by n points in 3-space, and in general in d dimensions. (i) The number of tetrahedra...
Selfish load balancing and atomic congestion games (2004)
Subhash Suri, Csaba D. T'oth, Yunhong Zhou
Abstract We revisit a classical load balancing problem in the modern context of decentralized systems andself-interested clients. In particular, there is a set of clients, each of whom must choose a...
Range counting over multidimensional data streams (2004)
Subhash Suri, Csaba D. T'oth, Yunhong Zhou
\Lambda \Lambda Abstract We consider the problem of approximate range counting over streams of d-dimensional points. In the data stream model, the algorithm makes a single scan of the data, which is...
Incidences of not-too-degenerate hyperplanes (1946)
Abstract We present a multi-dimensional generalization of the Szemer'edi-Trotter Theorem, and give asharp bound on the number of incidences of points and not-too-degenerate hyperplanes in...
Incidences of not-too-degenerate hyperplanes (1946)
Abstract We present a multi-dimensional generalization of the Szemer'edi-Trotter Theorem, and give a sharp bound on the number of incidences of points and not-too-degenerate hyperplanes in...