Csaba D. Tóth
Assistant Professor
Department of Mathematics and Statistics
University of Calgary, Room MS432
2500 University Drive, NW
Calgary, AB, Canada T2N 1N4
Phone: +1 (403) 220-3950
cdtoth ♠ math.ucalgary.ca

---

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

• On a question of Bourgain about geometric incidences,
  • József Solymosi and Csaba D. Tóth,
  • Combinatorics Probability and Computing 17 (4) (2008), 617-625.
  • (abstract) Given a set of s points and a set of n² lines in three-dimensional Euclidean space such that each line is incident to n points but no n lines are coplanar, then we have s=Ω(n^11/4). This is the first nontrivial answer to a question recently posed by Jean Bourgain.
• Extremal problems on triangle areas in the plane and three-space,
  • Adrian Dumitrescu, Micha Sharir, and Csaba D. Tóth,
  • Proc. 24nd ACM Sympos. Comput. Geom. (College Park, MD, 2008), ACM Press, pp. 208-217.
  • J. Combin. Theory Ser. A 116 (2009) 1177–1198.
  • (abstract) In the plane we prove: (i) The number of unit area triangles in the plane is O(n^44/19) =O(n^2.3158). The best previous bound, O(n^7/3), is due to Pach and Sharir from 1992. (ii) For points in convex position, there exist n-element point sets that span Ω(n log n) triangles of unit area. (iii) The number of triangles of minimum (nonzero) area determined by n points is at most (2/3)(n²-n); there exist n-element point sets that span (6/π²-o(1))n² minimum area triangles. (iv) The number of acute triangles of minimum area determined by n points is O(n); this is asymptotically tight. (v) For n points in convex position, the number of triangles of minimum area is O(n); this is asymptotically tight. (vi) If no three points are allowed to be collinear, there exist n-element point sets that span Ω(n log n) minimum area triangles. In three-space we prove: (i) The number of unit area triangles spanned by n points is at most O(n^17/7β(n)), where β(n) is an extremely slowly growing function. (ii) A set of n points, not all on a line, determines at least Ω(n^2/3/β(n)) triangles of distinct areas that share a common side. (iii) The number of minimum area triangles is O(n²); this is asymptotically tight. (iv) There exist n-element point sets that span Ω(n^4/3) triangles of maximum area.
• 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.
  • Combinatorics Probability and Computing 17 (2008), 203-224.
  • (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

• Binary plane partitions for disjoint line segments,
  • Csaba D. Tóth,
  • Proc. 25th Sympos. on Comput. Geom. (Aarhus, 2009), ACM Press, to appear.
  • (abstract) A binary space partition (BSP) for a set of disjoint objects in Euclidean space is a recursive decomposition, where each step partitions the space (and some of the objects) along a hyperplane and recurses on the objects clipped in each of the two open halfspaces. The size of a BSP is defined as the number of resulting fragments of the input objects. It is shown that every set of n disjoint line segments in the plane admits a BSP of size O(n log n/log log n). This bound is best possible apart from the constant factor.
• Stabbing numbers of convex subdivisions,
  • Csaba D. Tóth,
  • Periodica Mathematica Hungarica 57 (2) (2008), 217-225.
  • (abstract) It is shown that for every subdivision of the d-dimensional Euclidean space, d≥ 2, into n convex cells, there is a straight line that stabs at least Ω((log n,/loglog n)^1/(d-1)) cells. This bound is best possible apart from a constant factor. In other words, if a convex subdivision of d-space has the property that any line stabs at most k convex cells, then the subdivision has at most exp(O(k^{d-1}log k)) cells. Previously, this was only known in the case d=2.
• Axis-aligned 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.
  • SIAM J. Discrete Math. 22 (3) (2008), 1187-1204.
  • (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 (that is, stabs) at least Ω(log^1/(d-1)n) boxes. Constructions are also given for d≥2, where this bound is attained.
• 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 axis-aligned fat rectangles,
  • Csaba D. Tóth,
  • Proc. 11th European Symposium on Algorithms (Budapest, 2003), vol. 2832 of LNCS, Springer, Berlin, pp. 494-505.
  • SIAM J. Comput. 38 (1) (2008), 429-447.
• 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

• Tur\aacute;n-type results for partial orders and intersection graphs of convex sets,
  • by Jacob Fox, János Pach, and Csaba D. Tóth,
  • Israel J. of Math. (2007), to appear.
  • (abstract) We prove several Ramsey-type results for intersection graphs of arrangements geometric shapes in the plane. In particular, we prove the following bounds, all of which are tight apart from the constant c. There is a constant c>0 such that if n? N, n>2, and S is a family of convex bodies in the plane, then the intersection graph of S or its complement contains a complete bipartite graph with cn vertices in either of its vertex classes. There is a constant c>0 such that if n? N, n>2, and S is a family of x-monotone curves in the plane, then the intersection graph G of S contains a complete bipartite graph with cn/logn vertices in each of its vertex classes or the complement of G contains a complete bipartite graph with cn vertices in each of its vertex classes. Similar results were previously known for semialgebraic sets only, we show that algebraic properties are not necessary.
• 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 23 (5) (2007), 481-507.
  • (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), vol. 4619 of LNCS, Springer, pp. 470-482.
  • Discrete Comput. Geom. (2009), 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 4 (2) (2008), article 10.
  • (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

• Disjoint segments have a convex partition with a 2-edge connected dual graph,
  • Nadia M. Benbernou, Erik D. Demaine, Martin L. Demaine, Michael Hoffmann, Mashhood Ishaque, Diane L. Souvaine, and Csaba D. Tóth,
  • in Proc. 19th Canadian Conf. Comp. Geom. (Ottawa, ON, 2007), pp. 13-16.
    
• A bipartite strengthening of the Crossing Lemma,
  • by Jacob Fox, János Pach, and Csaba D. Tóth,
  • in Proc. 15th Sympos. on Graph Drawing (Sydney, 2007), vol. 4875 of LNCS, Springer, 2008, pp. 13-24.
    
  • (abstract) The celebrated Crossing Lemma states that, in every drawing of a graph with n vertices and m ≥ 4n edges there are at least &Omega(m³/n²) crossing edges; or equivalently, there is an edge that crosses &Omega(m²/n²) other edges. We strengthen the Crossing Lemma for drawings in which no two edges intersect in more than a constant number of points. We prove for every integer k that every graph G=(V,E) with n vertices and m ≥ 3n edges drawn in the plane such that any two edges intersect in at most k points has two disjoint subsets E₁,E₂ ⊂ E, each of size &Omega(m²/n²), such that every edge in E₁ crosses every edge in E₂. We also show that this result does not remain true if we drop the assumption that no pair of edges intersect in more than a constant number of points.
• 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.
  • Discrete Comput. Geom. (2007), to appear.
  • (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 98 (1) (2008), 33-42.
  • (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.
  • Comput. Geom. Theory Appl. 42 (5)(2009), 388-394.
  • (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. 39 (2008), 14-23.
• 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

• Convex partitions with 2-edge connected dual graphs,
  • Marwan Al-Jubeh, Michael Hoffmann, Mashhood Ishaque, Diane L. Souvaine, and Csaba D. Tóth,
  • in Abstracts of the 18th Fall Workshop on Comput. Geom. (Troy, NY, 2008), pp. 63-64.
  • in Proc. 15th Internat. Computing and Combin. Conf. (Niagara Falls, NY, 2009), LNCS, Springer, pp. 192-204.
  • (abstract) Every set of k disjoint convex polygonal obstacles with a total of n vertices in the plane, there is a partition of the free space into n-k+1 convex cells whose dual graph is 2-edge connected. Every convex cell corresponds to a node in the dual graph, and every vertex of an obstacle corresponds to an edge between two incident convex cells. We also refute a recent conjecture of Aicholzer et al. and present 15 disjoint segments such that if a convex partition is constructed by successively extending the segments along straight lines, then its dual graph has a bridge. Questions about the dual graph of a convex partition are motivated by the still unresolved conjecture about compatible disjoint geometric matchings.
• Shooting permanent rays among disjoint polygons in the plane,
  • Mashhood Ishaque, Bettina Speckmann, and Csaba D. Tóth,
  • Proc. 25th Sympos. on Comput. Geom. (Aarhus, 2009), ACM Press, to appear.
  • (abstract) We present a data structure for ray shooting and insertion in the free space among disjoint polygonal obstacles in the plane with a total of n vertices. The portion of each query ray between the starting point and the first obstacle hit is inserted permanently as a new obstacle. Our data structure uses O(n log n) space and preprocessing time, and it supports m successive ray shooting and insertion queries in O(n log n + m log m) total time. In contrast, if the query rays are not inserted as new obstacles, then m successive independent queries take O(m√n) time with currently known near-linear space data structures. Our data structure supports a near linear time computation of the convex partition of the free space around disjoint obstacles. If we are given disjoint polygons in the plane with a total of n vertices, a permutation of the reflex vertices, and a half-line at each reflex vertex that partitions the reflex angle into two convex angles, then the convex partitioning algorithm draws a ray emanating from each reflex vertex in the prescribed order in the given direction until it hits another obstacle, a previous ray, or infinity. The best previous implementation of the convex partition algorithm with a semi-dynamic ray shooting data structure in O(n^1+ε) space requires O(n^3/2-ε/2) time for any ε > 0. Our data structure improves the runtime of the convex partition algorithm to O(n log² n).
• Guarding curvilinear art galleries with vertex or point guards,
  • Menelaos I. Karavelas, Csaba D. Tóth, and Elias P. Tsigaridas,
  • Comput. Geom. Theory Appl. (2008), in press.
  • (abstract) It is shown that for monitoring a piecewise convex polygon with n ≥ 2 vertices, floor(2n/3) vertex guards are always sufficient and sometimes necessary. For the number of point guards that can be stationed at any point in the polygon, our upper bound floor(2n/3) carries over and we prove a lower bound of ceiling(n/2). For monitoring a piecewise concave polygon with n ≥ 3 vertices, 2n-4 point guards are always sufficient and sometimes necessary, whereas there are piecewise concave polygons where some points in the interior are hidden from all vertices, hence they cannot be monitored by vertex guards.
• 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

• On stars and Steiner stars II,
  • Adrian Dumitrescu, Csaba D. Tóth, and Guangwu Xu,
  • Proc. 20th ACM-SIAM Sympos. on Discrete Algorithms (New York, NY, 2009), ACM Press, pp. 311-317.
  • Discrete Optimization 6 (3) (2009), 324-332.
  • (abstract) A Steiner star for a set P of n points in d-space connects an arbitrary center point to all points of P, while a star connects a point p∈ P to the remaining n-1 points of P. All connections are realized by straight line segments. Fekete and Meijer showed that the minimum star is at most √2 times longer than the minimum Steiner star for any finite point configuration in d-space. The maximum ratio between them, over all finite point configurations in d-space, is called the star Steiner ratio in d-space. It is conjectured that this ratio is 4/π = 1.2732... in the plane and 4/3=1.3333... in three dimensions. Here we give upper bounds of 1.3631 in the plane, and 1.3833 in 3-space, thereby substantially improving recent upper bounds of 1.3999, and √2 -10^-4, respectively. (arxiv)
• Minimum weight convex Steiner partitions,
  • Adrian Dumitrescu and Csaba D. Tóth,
  • in Proc. 19th ACM-SIAM Sympos. on Discrete Algorithms (San Francisco, CA, 2008), ACM Press, pp. 581-590.
    
• On stars and Steiner stars,
  • Adrian Dumitrescu and Csaba D. Tóth,
  • in Proc. 19th ACM-SIAM Sympos. on Discrete Algorithms (San Francisco, CA, 2008), ACM Press, pp. 1233-1240.
    
• Analysis of two sweep-line algorithms for constructing spanning trees and Steiner trees,
  • Adrian Dumitrescu and Csaba D. Tóth,
  • in Abstracts of 17th Fall Workshop on Computational and Combinatorial Geometry (Hawthorne, NY, 2007).
    
  • J. Universal Comp. Sci., 13 (11)(2007), 1615-1627.
    
• 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