Csaba D. Tóth
Instructor in Applied Mathematics
Massachusetts Institute of Technology
77 Massachusetts Ave., Room 2-336
Cambridge, MA 02139
+1 (617) 253-6584
toth ♠ math.mit.edu

---

Publications:
1. Incidences, distance problems, and their relatives
2. Binary space partitions, stabbing numbers
3. Ramsey-type results in discrete geometry
4. Cuttings, ε-approximations, and arrangements
5. Spanning-trees, encompassing graphs, and crossings
6. Planar subdivisions, visibility, Art gallery problems
7. Networks, congestion games, fault tolerance

---

1. Incidences, distance problems, and their relatives

• Distinct triangle areas in a planar point set,
  • by Adrian Dumitrescu and Csaba D. Tóth,
  • Proc. 12th Conf. on Integer Programming and Optimization (Ithaca, NY, 2007), vol. 4513 of LNCS, Springer, pp. 119-129.
  • (abstract) (Erdős, Purdy, and Straus, 1977) conjectured that n noncollinear points in the plane determine at least ⌊(n-1)/2⌋ triangles of distinct areas. This bound is attained for equally spaced points distributed two parallel lines. We show that this number is at least 17n/38-O(1)≈ 0.4473n. The best previous bound, (√2 -1)n-O(1)≈0.4142n, follows from the combination of a results of (Burton and Purdy, 1979) and (Ungar, 1982). The new bound relies on considering consecutive elements in allowable sequences. (pdf)
• On the number of tetrahedra with minimal, unit, and distinct volumes in three-space,
  • Adrian Dumitrescu and Csaba D. Tóth,
  • Proc. 18th ACM-SIAM Sympos. on Discrete Algorithms (New Orleans, LA, 2007), ACM Press, pp. 1114-1123.
  • (abstract) We formulate and give partial answers to several combinatorial problems on four-tuples of n points in three-space. (i) The number of minimum (nonzero) volume tetrahedra spanned by n points in R³ is Θ(n³). (ii) The number of unit-volume tetrahedra determined by n points in R³ is O(n^7/2), and there are point sets for which this number is Ω(n³log log n). (iii) The tetrahedra determined by n points in R³, not all on a plane, have at least Ω(n) distinct volumes, and there are point sets for which this number is O(n); this gives a first partial answer for the three-dimensional case to an old question of Erdős, Purdy, and Straus. We also give an O(n³) time algorithm for reporting all tetrahedra of minimum nonzero volume, and thereby extend an early algorithm of Edelsbrunner, O'Rourke, and Seidel.
• Distinct distances in homogeneous sets in Euclidean space,
  • József Solymosi and Csaba D. Tóth,
  • Discrete Comput. Geom. 35 (4) (2006), 537-549.
  • (more) The minimum number of distinct distances determined by n points in d-space is between the upper bound O(n^2/d) (in the integer lattice section); and the lower bounds &Omega(n^2/d-2/d(d+2)) for d≥4 (Solymosi and Vu, 2005) and &Omega(n^.5460) in 3-space (Aronov, Pach, Sharir, and Tardos, 2004). In this paper, we improve all the above lower bounds for homogeneous point set, that is, when n points lie in cube of volume n and every unit cube contains O(1) points. Such a set of n points determines at least Ω(n^2d/(d2+1)) distinct distances in d-space and Ω(n^.6091) distinct distances in 3-space.
• Incidences of not-too-degenerate hyperplanes,
  • György Elekes and Csaba D. Tóth,
  • Proc. 21st ACM Sympos. Comput. Geom. (Pisa, 2005), ACM Press, pp. 16-21.
  • (more) We prove a new Szemerédi-Trotter-type bound on point-hyperplane incidences in d-space. One have to make some restriction on the incidences, otherwise m hyperplane can contain a line incident to all n points, the number of incidences is mn, and there's no non-trivial upper bound. In this paper we consider saturated hyperplanes only. In 3-space a plane containing k points is saturated if these points span at least Ω(k²) distinct lines. We show that the number of saturated planes containing k or more points is bounded by O(n^d/k^d+1+n^d-1/k^d-1). This is equivalent with the Szemerédi-Trotter Theorem for d=2, and it is tight for all d≥2. (ps) (pdf)
• The k most frequent distances in the plane,
  • József Solymosi, Gábor Tardos, and Csaba D. Tóth,
  • Discrete Comput. Geom., 28 (4) (2002), 639-648.
• Distinct distances in the plane,
  • József Solymosi and Csaba D. Tóth,
  • Proc. 17th ACM Sympos. on Comput. Geom. (Medford, MA, 2001), ACM Press, 2001, 29-31.
  • Discrete Comput. Geom. 25 (4) (2001), 629-634.

---

2. Binary space partitions, stabbing numbers

• Orthogonal subdivisions with low stabbing numbers,
  • Csaba D. Tóth,
  • Proc. 9th Workshop on Algorithms and Data Structures (Waterloo, ON, 2005), vol. 3608 of LNCS, Springer, pp. 256-268.
  • (more) An orthogonal subdivision in d-space is the partition of the space into axis-aligned boxes. It is shown that for any orthogonal subdivision of size n, there is an axis-parallel line that intersects the interior of (i.e., stabs) at least Ω(log^1/(d-1)n) boxes. Constructions are also given for d≥2, where this bound is attained. It is motivated by an interesting open problem: What is the minimum stabbing number of a convex subdivision in d-space, d≥3. In the plane, (Chazelle, Edelsbrunner, and Guibas, 1989) gave a tight bound of &Omega(log n/ log log n) for the stabbing number of convex subdivisions of size n.
• Binary space partitions: recent developments,
  • Csaba D. Tóth,
  • in Combinatorial and Computational Geometry, vol. 52 of MSRI Publications, Cambridge University Press, 2005, pp. 525-552.
• Binary space partition of orthogonal subdivisions,
  • John Hershberger, Subhash Suri, and Csaba D. Tóth,
  • Proc. 20th ACM Sympos. Comput. Geom. (Brooklyn, NY, 2004), ACM Press, pp. 230-238.
  • SIAM J. Comput. 34 (6) (2005), 1380-1397.
• Binary space partition for orthogonal fat rectangles,
  • Csaba D. Tóth,
  • Proc. 11th European Symposium on Algorithms (Budapest, 2003), vol. 2832 of LNCS, Springer, Berlin, pp. 494-505.
• Binary space partition for line segments with a limited number of directions,
  • Csaba D. Tóth,
  • Proc. 13th ACM-SIAM Sympos. on Discrete Algorithms (San Francisco, CA, 2002), ACM Press, 2002, 465-471.
  • SIAM J. Comput. 32 (2) (2003), 307-325.
• A note on binary plane partitions,
  • Csaba D. Tóth,
  • Proc. 17th ACM Sympos. on Comput. Geom. (Medford, MA, 2001), ACM Press, 2001, 151-156.
  • Discrete Comput. Geom. 30 (1) (2003), 3-16.

---

3. Ramsey-type results in discrete geometry

• Decompositions, partitions, and coverings with convex polygons and pseudo-triangles,
  
  • Oswin Aichholzer, Clemens Huemer, Sarah Kappes, Bettina Speckmann, and Csaba D. Tóth,
  • Proc. 31st Sympos. Math. Foundations Comp. Sci. (Stará Lesná, 2006), vol. 4162 of LNCS, Springer, pp. 86-97.
  • Graphs and Combinatorics (2007), to appear.
  • (abstract) We propose a novel subdivision of the plane that consists of both convex polygons and pseudo- triangles. This pseudo-convex decomposition is significantly sparser than either convex decompositions or pseudo-triangulations for planar point sets and simple polygons. We also introduce pseudo-convex partitions and coverings. We establish some basic properties and give combinatorial bounds on their complexity. Our upper bounds depend on new Ramsey-type results concerning disjoint empty convex k-gons in point sets. (pdf)
• Alternating paths along axis-parallel segments,
  • Csaba D. Tóth,
  • Abstracts of 19th European Wrokshop on Comput. Geom. (Bonn, 2003), pp. 133-136.
  • Proc. 8th Workshop on Algorithms and Data Structures (Ottawa, ON, 2003), vol. 2748 of LNCS, Springer, Berlin, 2003, pp. 389-400.
  • Graphs and Combinatorics 22 (2006), 527-543.
  • (ps) (pdf)
• Alternating paths through disjoint line segments,
  • Michael Hoffmann and Csaba D. Tóth,
  • Abstracts of the 18th European Workshop on Comput. Geom. (Warsaw, 2002),
  • Inform. Proc. Letts. 87 (6) (2003), 287-294.

---

4. Cuttings, ε-approximations, and arrangements

• Cuttings for disks and axis-aligned rectangles in three-space,
  • Eynat Rafalin, Diane L. Souvaine, and Csaba D. Tóth,
  • Proc. 10th Workshop on Algorithms and Data Structures (Halifax, NS, 2007), LNCS, Springer, to appear.
  • (abstract) For n objects in Euclidean space and an integer 1≤r≤n an (1/r)-cutting is a partition of the space into simplices such that the interior each simplex intersects at most n/r objects. Cuttings play a central role in proofs based on a divide-and-conquer strategy (for example, incidence bounds and range counting). Tight bounds are known for the cuttings of hyperplanes in dspace, for any d≥2 (Chazelle and Friedman, 1990). However, little seems to be known about cuttings for disjoint objects. We show that there is an (1/r)-cutting of size O(r²) for every finite set of disjoint disks in 3-space; and there is an (1/r)-cutting of size O(r^3/2) for every finite set of disjoint axis-aligned rectangles in 3-space. Both bounds are best possible.
• Detecting cuts in sensor networks,
  • Nisheeth Shrivastava, Subhash Suri, and Csaba D. Tóth,
  • Proc. 4th International Conference on Information Processing in Sensor Networks (Los Angeles, CA, 2005), IEEE, pp. 210-217.
  • Transactions on Sensor Networks (2007), to appear.
  • (more) This is a result about "two-sided" ε-nets. Given a set P of n points in the plane, an ε-sentinel set is a subset S⊆P such that for every directed query line L we can decide whether at least ε|P| points of less than ε|P|/2 lie on the left side of L based on how L partitions the sentinel set S. By contrast, if ε|P| points are on the left side of L, then a point of any ε-net N must also be on the that side; but if a point of N is on the left side of L, then there might be as few as just one point on that side. We show that there is an ε-sentinel set of size O(1/ε) for every set of n points in the plane, which is best possible, and we propose efficient algorithms to compute an ε-sentinel set of size O(1/ε).
• Space complexity of hierarchical heavy hitters in multi-dimensional data streams,
  • John Hershberger, Nisheeth Shrivastava, Subhash Suri, and Csaba D. Tóth,
  • Proc. 24th Sympos. on Principles of Database Systems (Baltimore, MD, 2005), ACM Press, pp. 338-347.
  • (abstract) Heavy hitters are items occurring with frequency above a given threshold, they are an important aggregation and summary tool for processing data streams. Hierarchical heavy hitters (HHHs) have been introduced as a generalization for hierarchical data domains, including multi-dimensional data. An item x in a hierarchy is called a φ-HHH if its frequency after discounting the frequencies of all its descendant hierarchical heavy hitters exceeds φn, where φ is a user-specified parameter and n is the size of the data set. Recently, single-pass schemes have been proposed for computing φ-HHHs using space roughly O(log(φn)/φ). The frequency estimates of these algorithms, however, hold only for the total frequencies of items, and not the discounted frequencies; this leads to false positives because the discounted frequency can be significantly smaller than the total frequency. This paper attempts to explain the difficulty of finding hierarchical heavy hitters with better accuracy. We show that a single-pass deterministic scheme that computes φ-HHHs in a d-dimensional hierarchy with any approximation guarantee must use Ω(1/φ^d+1) space. This bound is tight: we present a data stream algorithm that can report the φ-HHHs without false positives in O(1/φ^d+1) space.
• Adaptive spatial partitioning for multidimensional data streams,
  • John Hershberger, Nisheeth Shrivastava, Subhash Suri, and Csaba D. Tóth,
  • Proc. 15th International Symposium on Algorithms and Computation (Hong Kong, 2004), vol. 3341 of LNCS, Springer, pp. 522-533.
  • Algorithmica 46 (2006), 97-117.
• Range counting over multidimensional data streams,
  • Subhash Suri, Csaba D. Tóth, and Yunhong Zhou,
  • Proc. 20th ACM Sympos. Comput. Geom. (Brooklyn, NY, 2004), ACM Press, pp. 160-169.
  • Discrete Comput. Geom. 36 (2006), 633-655.
    

---

5. Spanning-tress, encompassing graphs, and crossings

• Tight bounds for connecting sites across barriers,
  • David Krumme, Eynat Rafalin, Diane L. Souvaine, and Csaba D. Tóth,
  • Proc. 22nd ACM Sympos. Comput. Geom. (Sedona, AZ, 2006), ACM Press, pp. 439-448.
  • (more) This result was motivated by a multi-point location problem, a central question in computational geometry. Assume that we are given n pairwise non-crossing line segments in the plane that subdivides the plane into n+1 convex cells, and we are also a point in the interior of each cell. Then these n+1 points can be connected by a straight line spanning tree such that every line segment crosses at most two edges of the tree. There is also a spanning tree such that the total number of segment-edge crossings is at most 5n/3+O(√n). Both bounds are best possible.
• Spanning trees across axis-parallel segments,
  • Michael Hoffmann and Csaba D. Tóth,
  • Proc. 18th Canadian Conf. Comput. Geom. (Kingston, ON, 2006), pp. 101-104.
  • (more) This paper proves a similar result to the previous one. Given n disjoint axis-parallel line segments in the plane and a set of points (also disjoint from the segments), the points can be connected by a straight line spanning tree such that every line segment crosses at most three edges of the tree. The bound three cannot be improved. If we drop the condition on the direction of the segments, then no tight bound is known.
• On the decay of crossing numbers,
  • Jacob Fox and Csaba D. Tóth,
  • Proc. 14th Sympos. on Graph Drawing (Karlsruhe, 2006), vol. 4372 of LNCS, Springer, pp. 174-183.
  • J. Combin. Theory Ser. B (2007), to appear
  • (more) Our research is motivated by an old conjecture of (Richter and Thomassen, 1993) that says that every graph has an edge such that the removal of this edge decreases the crossing number by an amount proportional to the square root of the crossing number. We show here that one can remove a constant fraction of the edges so that the crossing number also decreases by at most a constant factor. Along the way, we also prove a new lower bound on the crossing number in terms of the sum of degree squares.
• Pointed and colored binary encompassing trees,
  • Michael Hoffmann and Csaba D. Tóth,
  • Proc. 21st ACM Sympos. Comput. Geom. (Pisa, 2005), ACM Press, pp. 81-90.
  • (more) This is a generalization of several previous results on augmenting planar straight line graphs (Bose, Houle, and Toussaint, 2001) and on bounded degree spanning trees for colored points in the plane (Kaneko, 2000). Assume that we are given a disconnected vertex-colored planar straight line graph G, with no singleton component. We want to augment G to a connected graph G', G⊆G', by adding new straight line edges that respect the coloring and keep the graph plane. It is shown that this can be done so that the degree of every vertex increases by at most two. The bound two is best possible.
• A vertex-face assignment for plane graphs,
  • Diane L. Souvaine and Csaba D. Tóth,
  • Proc. 17th Canadian Conf. on Comput. Geom. (Windsor, ON, 2005), pp. 131-134.
  • (more) We show an interesting relation between the faces and vertices of a planar straight line graph. Every face can be assigned to an incident vertex such that every vertex is assigned to at most two faces, and every reflex vertex is assigned to at most one face. (A vertex is reflex if it is the apex of a reflex angle in an incident face.) It was used to prove the above result on vertex-colored encompassing graphs for arbitrary planar straight line graphs (without this result, it would hold only for plane forests, graphs with a single face). The proof relies on a new construction of combinatorial pseudo-triangulations by (Haas et al., 2005), extending Henneberg operations.
• Pointed binary encompassing trees: simple and optimal,
  • Michael Hoffmann, Bettina Speckmann, and Csaba D. Tóth,
  • Abstracts of 14th Annual Fall Workshop on Computational Geometry (Cambridge, MA, 2004), pp. 28-29.
  • Abstracts of 21st European Workshop on Comput. Geom. (Eidhoven, 2005), pp. 93-96.
  • Comput. Geom. Theory Appl. (2007), to appear.
• Encompassing colored crossing-free geometric graphs,
  • Ferran Hurtado, Mikio Kano, David Rappaport, and Csaba D. Tóth,
  • Proc. 16th Canadian Conf. Comput. Geom. (Montréal, QC, 2004), pp. 48-52.
  • Comput. Geom. Theory Appl. (2006), to appear.
• Pointed binary encompassing trees,
  • Michael Hoffmann, Bettina Speckmann, and Csaba D. Tóth,
  • Abstracts of 20th European Workshop on Comput. Geom. (Seville, 2004), pp. 131-314.
  • Proc. 9th Scandinavian Workshop on Algorithm Theory (Humlebæk, 2004), vol. 3111 of LNCS, Springer, pp. 442-454.
• Degree bounds for constrained pseudo-triangulations,
  • Oswin Aichholzer, Michael Hoffmann, Bettina Speckmann, and Csaba D. Tóth,
  • Proc. 15th Canadian Conf. Comput. Geom. (Halifax, NS, 2003), pp. 155-158.

---

6. Planar subdivisions, visibility, Art gallery problems

• Allocating vertex π-guards in simple polygons via pseudo-triangulations,
  • Bettina Speckmann and Csaba D. Tóth,
  • Proc. 14th ACM-SIAM Sympos. on Discrete Algorithms (Baltimore, MD, 2003), ACM Press, 2003, 109-118.
  • Discrete Comput. Geom. 33 (2) (2005), 345-364.
• Illuminating disjoint line segments in the plane,
  • Csaba D. Tóth,
  • Discrete Comput. Geom. 30 (3) (2003), 489-505.
• Illumination in the presence of opaque line segments in the plane,
  • Csaba D. Tóth,
  • Comput. Geom. Theory Appl. 21 (3) (2002), 193-204.
• Art galleries with guards of uniform range of vision,
  • Csaba D. Tóth,
  • Comput. Geom. Theory Appl. 21 (3) (2002), 185-192.
• Segment endpoint visibility graphs are Hamiltonian,
  • Michael Hoffmann and Csaba D. Tóth,
  • Proc. 13th Canadian Conference on Comput. Geom. (Waterloo, ON, 2001), 109-112.
  • Comput. Geom. Theory Appl. 26 (1) (2003), 47-68.
• Illuminating polygons with vertex π-floodlights,
  • Csaba D. Tóth,
  • Proc. Int. Conf. on Comput. Sci. (San Francisco, CA, 2001) Part I, vol, 2073 of LNCS, Springer, Berlin, 2001, pp. 772-781.
• Guarding disjoint triangles and claws in the plane,
  • Csaba D. Tóth,
  • Abstracts of the 17th European Workshop on Comput. Geom. (Berlin, 2001),
  • Comput. Geom. Theory Appl. 25 (1-2) (2003), 51-65.
• Illuminating both sides of line segments,
  • Csaba D. Tóth,
  • in: Discrete and Computational Geometry (J. Akiyama, M. Kano, M. Urabe, eds.), vol. 2098 of LNCS, Springer, Berlin, 2001, pp. 370-380.
• Illuminating labyrinths,
  • Csaba D. Tóth,
  • Abstracts of Optimal Discrete Structures and Algorithms (Rostock, 2000).
  • Discrete Appl. Maths. 138 (1-2) (2004), 215-228.
• Art gallery problem with guards whose range of vision is 180º,
  • Csaba D. Tóth,
  • Comput. Geom. Theory Appl. 17 (3-4) (2000), 121-134.
• Illumination of polygons 45º-floodlights,
  • Csaba D. Tóth,
  • Presented at 4th Geometry Festival (Budapest, 1999).
  • Discrete Maths. 265 (1-3) (2003), 251-260.

---

7. Networks, congestion games, fault tolerance

• Improved throughput bounds for interference-aware wireless networks,
  • by Chiranjeeb Buragohain, Subhash Suri, Csaba D. Tóth, and Yunhong Zhou,
  • Proc. 13th Computing and Combinatorics Conference (Banff, AB, 2007), vol. 4598 of LNCS, Springer, pp. 210-221.
• Light orthogonal networks with constant geometric dilation,
  • Adrian Dumitrescu and Csaba D. Tóth,
  • Proc. 24th Sympos. Theoretical Aspects of Comp. Sci. (Aachen, 2007), vol. 4393 of LNCS, Springer, pp. 175-187.
  • (abstract) An orthogonal network for a given set of n points in the plane is an axis-aligned planar straight line graph that connects all input points. We show that for any set of n points in the plane, there is an orthogonal network that (i) is short having a total edge length of O(|T|), where |T| denotes the length of a minimum Euclidean spanning tree for the point set; (ii) is small having O(n) vertices and edges; and (iii) has bounded geometric dilation, which means that for any two points u and v in the network, the shortest path in the network between u and v is at most constant times longer than the (Euclidean) distance between u and v.
• Selfish load balancing and atomic congestion games,
  • Subhash Suri, Csaba D. Tóth, and Yunhong Zhou,
  • Proc. 16th ACM Sympos. on Parallelism in Algorithms and Architectures (Barcelona, 2004), ACM Press, 2004, pp. 188-195.
  • Algorithmica 47 (1) (2007), 79-96.
    
  • (ps) (pdf)
• Congestion games, load balancing, and price of anarchy,
  • Anshul Kothari, Subhash Suri, Csaba D. Tóth, and Yunhong Zhou,
  • Proc. Workshop on Combinatorial and Algorithmic Aspects of Networking (Banff, AB, 2004), vol. 3405 of LNCS, Springer, 2005, pp. 13-27.
• Uncoordinated load balancing and congestion games in P2P systems,
  
  • Subhash Suri, Csaba D. Tóth, and Yunhong Zhou,
  • Proc. 3rd Internat. Workshop on Peer-to-Peer Systems (La Jolla, CA, 2004), vol. 3279 of LNCS, Springer, pp. 123-130.
• Fault tolerant on-board networks with priorities,
  • Jean-Claude Bermond, Frédéric Havet, and Csaba D. Tóth,
  • in 3rd AlgoTel (Saint-Jean-de-Luz, 2001), pp. 95-98.
  • Networks 47 (1) (2006), 9--25.
• All-to-all routing and coloring in weighted trees of rings,
  • Bruno Beauquier, StéphanePérennes, and David Tóth,
  • Proc. 11th ACM Sympos. on Parallel Algorithms and Architectures (Saint-Malo, 1999), ACM Press, 1999, 185-190.

---

---

Manuscripts