Csaba D. Tóth
Department of Mathematics
California State University, Northridge
Room SN 434, 18111 Nordhoff St.
Northridge, CA 91330-8313
P\hone: (818) 677-2826
cdtoth ♠ acm.org

---

Publications
in reverse chronological order (see also DBLP)

• Minimum plane bichromatic spanning trees,
  • Hugo A. Akitaya, Ahmad Biniaz, Erik D. Demaine, Linda Kleist, Frederick Stock, and Csaba D. Tóth,
  • in Proc. 35th International Symposium on Algorithms and Computation (Sydney, 2024), LIPIcs, to appear.
  
  
• Towards instance-optimal Euclidean spanners,
  • Hung Le, Shay Solomon, Cuong Than, Csaba D. Tóth, and Tianyi Zhang,
  • in Proc.65th IEEE Symposium on Foundations of Computer Science (Chicago, IL, 2024), to appear.
  
  
• Noncrossing longest paths and cycles,
  • Greg Aloupis, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, David Eppstein, Anil Maheshwari, Saeed Odak, Michiel Smid, Csaba D. Tóth, and Pavel Valtr,
  • in Proc. 32nd Symposium on Graph Drawing and Network Visualization (Vienna, 2024), LIPIcs, Schloss Dagstuhl, to appear.


• Nonrealizable planar and spherical occlusion diagrams,
  • Kimberly Kokado and Csaba D. Tóth,
  • Preliminary version in Abstract of the Japanese Conf. Discrete and Comp. Geom. Graphs, and Games (JCDCG³) (Tokyo, 2022), pp. 60-61.
  • in Discrete and Computational Geometry. Graphs, and Games (selected papers from JCDCGGG 2022), LNCS, Springer, 2024, to appear.


• Fully dynamic maximum independent sets of disks in polylogarithmic update time,
  • Sujoy Bhore, Martin Nöllenburg, Csaba D. Tóth, and Jules Wulms
  • Preliminary version in Abstracts of 40th European Workshop on Computational Geometry (Ioannina, 2024), pp. 13:1-13:8, pp. 43:1-43:8.
  • in Proc. 40th Sympos. Comput. Geom. (Athens, 2024), LIPIcs 293, Schloss Dagstuhl, pp. 19:1-19:16.


• Plane multigraphs with one-bend and circular-arc edges of a fixed angle,
  
  • Csaba D. Tóth,
  • in Proc. 18th International Conference and Workshop on Algorithms and Computation (Kanazawa, 2024), LNCS 14549, Springer, pp. 15-31.


• Online duet between metric embeddings and minimum-weight perfect matchings,
  • Sujoy Bhore, Arnold Filtser, and Csaba D. Tóth,
  • in Proc. 34th ACM-SIAM Sympos. on Discrete Algorithms (Alexandria, VA, 2024), pp. 4564-4579.


• Minimizing visible edges in polyhedra,
  • Csaba D. Tóth, Jorge Urrutia, and Giovanni Viglietta,
  • Graphs and Combinatorics 39(5) (2023), article 111.


• On RAC drawings of graphs with two bends per edge,
  • Csaba D. Tóth,
  • in Proc. 31st Symposium on Graph Drawing and Network Visualization (Isola delle Femmine, 2023), LNCS 14465, Springer, pp. 69–77.
  • Journal of Graph Algorithms and Applications 28 (2) (2024), 37-45.
  
  
• Reconfiguration of polygonal subdivisions via recombination,
  • Hugo Akitaya, Andrei Gonczi, Diane Souvaine, Csaba D. Tóth, and Thomas Weighill,
  • Preliminary version in Abstracts of 2nd Workshop on Combinatorial Reconfiguration (Paris, 2022).
  • in Proc. 31st European Symposium on Algorithms (Amsterdam, 2023), LIPIcs 274, Schloss Dagstuhl, 6:1-16.
  
  
• Observation routes and external watchman routes,
  • Adrian Dumitrescu and Csaba D. Tóth,
  • in Proc. 18th Algorithms and Data Structures Symposium (Montréal, QC, 2023), LNCS 14079, Springer, pp. 401-415.
  • Theoretical Computer Science 1019 (2024), 114818.


• Maximal distortion of geodesic diameters in polygonal domains,
  • Adrian Dumitrescu and Csaba D. Tóth,
  • Preliminary version "Geodesic diameter in polygons with holes" in Proc. 12th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications (Budapest, 2023), pp. 543-548.
  • in Proc. 34th International Workshop on Combinatorial Algorithms (Tainan, 2023), LNCS 13889, Springer, pp. 197–208.


• Online spanners in metric spaces,
  • Sujoy Bhore, Arnold Filtser, Hadi Khodabandeh, and Csaba D. Tóth,
  • in Proc. 30th European Symposium on Algorithms (Potsdam, 2022), LIPIcs 244, Schloss Dagstuhl, 18:1-20.
  • SIAM J. Discrete Math. 38(1) (2024), pp. 1030-1056.


• Minimum weight Euclidean (1+ε)-spanners,
  • Csaba D. Tóth,
  • in Proc. 48th Workshop on Graph-Theoretic Concepts in Computer Science (Tübingen, 2022), LNCS 13453, Springer, pp. 439-452.
  • European J. Combin. 118 (2024), 103927.


• Hop spanners for geometric intersection graphs,
  • Jonathan Conroy and Csaba D. Tóth,
  • in Proc. 38th International Symposium on Computational Geometry (Berlin, 2022), LIPIcs 224, Schloss Dagstuhl, pp. 30:1-17.
  • J. Comput Geom. 14 (2) (2023), 26-64.


• Reconfiguration of connected graph partitions,
  • Hugo A. Akitaya, Matthew D. Jones, Matias Korman, Christopher Meierfrankenfeld, Michael J. Munje, Diane L. Souvaine, Michael Thramann, and Csaba D. Tóth,
  • J. Graph Theory 102(1) (2023), 35-66.


• Aspect ratio universal rectangular layouts,
  • Stefan Felsner, Andrew Nathenson, and Csaba D. Tóth,
  • in Proc. 16th International Conference and Workshops on Algorithms and Computation (Jember, 2022), LNCS 13174, Springer, pp. 73-84.
  • Computing in Geometry and Topology 3 (1) (2024), 3:1–3:24.


• Online Euclidean spanners,
  • Sujoy Bhore and Csaba D. Tóth,
  • in Proc. 29th European Symposium on Algorithms (Lisbon, 2021), LIPIcs 204, Schloss Dagstuhl, pp. 16:1-19
  • ACM Transactions on Algorithms (2024), to appear.


• Euclidean Steiner spanners: Light and sparse,
  • Sujoy Bhore and Csaba D. Tóth,
  • SIAM Discrete Math. 36(3) (2022), 2411-2444,
  • This combines results from two conference papers:
  • Light Euclidean Steiner spanners in the plane, in Proc. 37th International Symposium on Computational Geometry (Buffalo, NY, 2021), LIPIcs 189, Schloss Dagstuhl, pp. 15:1-15:17;
  • On Euclidean Steiner (1+ε)-spanners, in Proc. 38th Symposium on Theoretical Aspects of Computer Science (Saarbrücken, 2021), LIPIcs 187, Schloss Dagstuhl, pp. 13:1-16.


• Reconfiguration of connected graph partitions via recombination,
  • Hugo A. Akitaya, Matias Korman, Oliver Korten, Diane L. Souvaine, and Csaba D. Tóth,
  • in Proc. 12th International Conference on Algorithms and Complexity (Larnaca, 2021), LNCS 12701, Springer, pp. 61-74.
  • Theoretical Computer Science 923 (2022), 13-26.


• Quantitative restrictions on crossing patterns,
  • Csaba D. Tóth,
  • in Beyond Planar Graphs (Seok-Hee Hong and Takeshi Tokuyama, eds.), Communications of NII Shonan Meetings, Springer, Singapore, 2020, pp. 11-29.


• Sparse hop spanners for unit disk graphs,
  • Adrian Dumitrescu, Anirban Ghosh, and Csaba D. Tóth,
  • in Proc. 31st International Symposium on Algorithms and Computation (Hong Kong, 2020), LIPIcs 181, Schloss Dagstuhl, article 57.
  • Computational Geometry: Theory and Computing 100 (2022), 101808.


• Simple topological drawings of k-planar graphs,
  • Michael Hoffmann, Chih-Hung Liu, Meghana M. Reddy, and Csaba D. Tóth,
  • Preliminary version in Abstracts of 36th European Workshop on Computational Geometry (Würzburg, 2020), pp. 80:1-80:6.
  • in Proc. 28th International Symposium on Graph Drawing and Network Visualization (Vancouver, BC, 2020), LNCS 12590, Springer, 2021, pp. 390-402.
  
  
• Polygons with prescribed angles in 2D and 3D,
  • Alon Efrat, Radoslav Fulek, Stephen Kobourov, and Csaba D. Tóth,
  • in Proc. 28th International Symposium on Graph Drawing and Network Visualization (Vancouver, BC, 2020), LNCS 12590, Springer, 2021, pp. 135-147.
  • Journal of Graph Algorithms and Applications 26 (3) (2022), 363-380.


• 2048 without merging,
  • Hugo Akitaya, Erik D. Demaine, Jason S. Ku, Jayson Lynch, Mike Paterson, and Csaba D. Tóth,
  • in Proc. 32nd Canadian Conference on Computational Geometry (Saskatoon, SK, 2020).


• Cutting polygons into small pieces with chords: Laser-based localization,
  • Esther Arkin, Rathish Das, Jie Gao, Mayank Goswami, Joseph S.B. Mitchell, Valentin Polishchuk, and Csaba D. Tóth,
  • Preliminary version: Esther Arkin, Peter Brass, Rathish Das, Jie Gao, Mayank Goswami, Joseph S.B. Mitchell, Valentin Polishchuk, and Csaba D. Tóth, Optimal cutting of a polygon by lasers, in Abstracts of the 26th Fall Workshop on Computational Geometry (New York, NY, 2016).
  • in Proc. 28th European Symposium on Algorithms (Pisa, 2020), LIPIcs 173, Schloss Dagstuhl, article 7.


• Universal geometric graphs,
  • Fabrizio Frati, Michael Hoffmann, and Csaba D. Tóth,
  • in Proc. 46th Workshop on Graph-Theoretic Concepts in Computer Science (Leeds, 2020), LNCS 12301, Springer, pp 174-186.
  • Combinatorics, Probability, and Computing 32 (5) (2023), 742-761.


• Atomic embeddability, clustered planarity, and thickenability,
  • Radoslav Fulek and Csaba D. Tóth,
  • in Proc. 31st ACM-SIAM Symposium on Discrete Algorithms (Salt Lake City, UT, 2020), pp. 2876-2895.
  • JACM 69 (2) (2022), article 13.


• On the Cover of the Rolling Stone,
  • Adrian Dumitrescu and Csaba D. Tóth,
  • in Proc. 31st ACM-SIAM Symposium on Discrete Algorithms (Salt Lake City, UT, 2020), pp. 2575-2586.


• Simple k-planar graphs are (k+1)-quasiplanar,
  • Patrizio Angelini, Michael A. Bekos, Franz J. Brandenburg, Giordano Da Lozzo, Giuseppe Di Battista, Walter Didimo, Michael Hoffmann, Giuseppe Liotta, Fabrizio Montecchian, and Csaba D. Tóth,
  • Preliminary version: Michael Hoffmann and Csaba D. Tóth, Two-planar graphs are quasiplanar in Proc. 42nd Symposium on Mathematical Foundations of Computer Science (Aalborg, 2017), LIPIcs 83, Schloss Dagstuhl, article 47.
  • J. Combin. Theory Ser. B 142 (2020), 1-35.
  • (abstract) A simple topological graph is k-quasiplanar (k≥ 2) if it contains no k pairwise crossing edges, and k-planar if no edge is crossed more than k times. In this paper, we explore the relationship between k-planarity and k-quasiplanarity to show that, for k≥2, every k-planar simple topological graph can be transformed into a (k+1)-quasiplanar simple topological graph.


• On the stretch factor of a polygonal chain,
  • Ke Chen, Adrian Dumitrescu, Wolfgang Mulzer, and Csaba D. Tóth,
  • in Proc. 44th Symposium on Mathematical Foundations of Computer Science (Aachen, 2019), LIPIcs 138, article 56.
  • SIAM J. Discrete Math. 35 (3) (2021), 1592-1614.


• Rock climber distance: Frogs versus dogs,
  • Hugo A. Akitaya, Leonie Ryvkin, and Csaba D. Tóth,
  • in Proc. 31st Canadian Conference on Computational Geometry (Edmonton, AB, 2019), pp. 210-217.


• Hamiltonian meander paths and cycles on bichromatic point sets,
  • Oswin Aichholzer, Carlos Alegría, Irene Parada, Alexander Pilz, Javier Tejel, Csaba D. Tóth, Jorge Urrutia, and Birgit Vogtenhuber,
  • in Abstracts of the XVIII Spanish Meeting on Computational Geometry (Girona, 2019), pp. 35-38.


• Rainbow polygons for colored point sets in the plane,
  • David Flores-Peñaloza, Mikio Kano, Leonardo Martínez-Sandoval, David Orden, Javier Tejel, Csaba D. Tóth, Jorge Urrutia, and Birgit Vogtenhuber,
  • in Abstracts of the XVIII Spanish Meeting on Computational Geometry (Girona, 2019), pp. 43-46.
  • Discrete Mathematics 344 (7) (2021), 112406.


• Circumscribing polygons and polygonizations for disjoint line segments,
  • Hugo Akitaya, Matias Korman, Oliver Korten, Mikhail Rudoy, Diane Souvaine, and Csaba D. Tóth,
  • Preliminary version in Proc. 35th Symposium on Computational Geometry (Portland, OR, 2019), LIPIcs 129, article 9.
  • Discrete Comput. Geom. 68 (2022), 218-254.


• Convex polygons in Cartesian products,
  • Jean-Lou De Carufel, Adrian Dumitrescu, Wouter Meulemans, Tim Ophelders, Claire Pennarun, Csaba D. Tóth, and Sander Verdonschot,
  • Preliminary version in the Abstracts of the 34th European Workshop on Computational Geometry (Berlin, 2018).
  • in Proc. 35th Symposium on Computational Geometry (Portland, OR, 2019), LIPIcs 129, article 22.
  • Journal of Computational Geometry 11(2) (2020), 205-233.


• Reconstruction of the crossing type of a point set from the compatible exchange graph of noncrossing spanning trees,
  • Marcos Oropeza and Csaba D. Tóth,
  • in Proc. 21st IAPR International Conference on Discrete Geometry for Computer Imagery (Paris, 2019), LNCS 11414, Springer, 2019, pp. 234-245.
  • Information Processing Letters 170 (2021), 106116.


• Online unit covering in Euclidean space,
  • Adrian Dumitrescu, Anirban Ghosh, and Csaba D. Tóth,
  • in Proc. 12th Conference on Combinatorial Optimization and Applications (Atlanta, GA, 2018), LNCS 11346, Springer, pp. 609-623.
  • Theoretical Computer Science 809 (2020), 218-230.


• Improved bounds on information dissemination by Manhattan random waypoint model,
  • Aria Rezaei, Jie Gao, Jeff Phillips, and Csaba D. Tóth,
  • in Proc. 26th ACM SIGSPATIAL Int. Conf. on Advances in Geographic Information Systems (Seattle, WA, 2018), pp. 139-148.


• Crossing minimization in perturbed drawings,
  • Radoslav Fulek and Csaba D. Tóth,
  • in Proc. 26th Symposium on Graph Drawing & Network Visualization (Barcelona, 2018), LNCS 11282, Springer, pp. 229-241.
  • J. Combin. Opt. 40 (2020), 279-302.
  • (abstract) Due to data compression or low resolution, nearby vertices and edges of a graph drawing may be bundled to a common node or arc. We model such a "compromised"' drawing by a piecewise linear map φ:G→R². We wish to perturb φ by an arbitrarily small ε>0 into a proper drawing (in which the vertices are distinct points, any two edges intersect in finitely many points, and no three edges have a common interior point) that minimizes the number of crossings. An ε-perturbation, for every ε>0, is given by a piecewise linear map ψ_ε:G→R² with |φ-ψ_ε|<ε, where |.| is the uniform norm (i.e., sup norm). We present a polynomial-time solution for this optimization problem when G is a cycle and the map φ has no spurs (i.e., no two adjacent edges are mapped to overlapping arcs). We also show that the problem becomes NP-complete (i) when G is an arbitrary graph and φ has no spurs, and (ii) when φ may have spurs and G is a cycle or a union of disjoint paths.


• Compatible paths on labelled point sets,
  • Yeganeh Bahoo, Ahmad Biniaz, Pilar Cano, Farah Chanchary, John Iacono, Kshitij Jain, Elena Khramtcova, Anna Lubiw, Debajyoti Mondal, Khadijeh Sheikhan, and Csaba D. Tóth,
  • in Proc. 30th Canadian Conference on Computational Geometry (Winnipeg, MB, 2018), pp. 54-60.
  • (abstract) Let P and Q be finite point sets of the same cardinality in R², each labelled from 1 to n. Two noncrossing geometric graphs G_P and G_Q spanning P and Q, respectively, are called compatible if for every face f in G_P, there exists a corresponding face in G_Q with the same clockwise ordering of the vertices on its boundary as in f. In particular, G_P and G_Q must be straight-line embeddings of the same connected n-vertex graph G. No polynomial-time algorithm is known for deciding whether two labelled point sets admit compatible geometric graphs. The complexity of the problem is open, even when the graphs are constrained to be triangulations, trees, or simple paths.
    We give polynomial-time algorithms to find compatible paths or report that none exist in three scenarios: O(n) time for points in convex position; O(n²) time for two simple polygons, where the paths are restricted to remain inside the closed polygons; and O(n² log n) time for points in general position if the paths are restricted to be monotone.


• Maximum area axis-aligned square packings,
  • Hugo A. Akitaya, Matthew D. Jones, David Stalfa, and Csaba D. Tóth,
  • in Proc. 43rd Symposium on Mathematical Foundations of Computer Science (Liverpool, 2018), LIPIcs 117, Schloss Dagstuhl, pp. 77:1--77:15.
  • Discrete Opt. 37 (2020), 100580.
  • (abstract) Given a point set S={s₁,...,s_n} in the unit square U=[0,1]², an anchored square packing is a set of n interior-disjoint squares in U such that s_i is a corner of the ith square. The reach R(S) of S is the set of points that may be covered by such a packing (i.e., the union of all squares anchored at points in S). It is shown that area(R(S))≥1/2 for every S⊂U, and this bound is the best possible. The region R(S) can be computed in O(n log n) time. Finally, we show that finding a maximum area anchored square packing is NP-complete. This is the first hardness proof for a square packing problem where the possible sizes of the squares are not part of the input.


• Transition operations over plane trees,
  • Torrie L. Nichols, Alexander Pilz, Csaba D. Tóth, and Ahad N. Zehmakan,
  • in Proc. 13th Latin American Theoretical INformatics Symposium (Buenos Aires, 2018), LNCS 10807, Springer, pp. 835-838.
  • Discrete Math. 343 (8) (2020), 111929.
  • (abstract) The operation of transforming one spanning tree into another by replacing an edge has been considered widely, both for general and geometric graphs. For the latter, several variants have been studied (e.g., edge slides and edge rotations). In a transition graph on the set T (S) of noncrossing straight-line spanning trees on a finite point set S in the plane, two spanning trees are connected by an edge if one can be transformed into the other by such an operation. We study bounds on the diameter of these graphs, and consider the various operations both on general point sets and sets in convex position. In addition, we address the problem variant where operations may be performed simultaneously. We prove new lower and upper bounds for the diameters of the corresponding transition graphs and pose open problems.


• Recognizing weak embeddings of graphs,
  • Hugo A. Akitaya, Radoslav Fulek, and Csaba D. Tóth,
  • in Proc. ACM-SIAM Symposium on Discrete Algorithms (New Orleans, LA, 2018), pp. 274-292.
  • ACM Transactions on Algorithms 15(4) (2019), article 50.
  • (abstract) We present an efficient algorithm for a problem in the interface between clustering and graph embeddings. An embedding φ:G→M of a graph G into a manifold M maps the vertices in V(G) to distinct points and the edges in E(G) to interior-disjoint Jordan arcs between the corresponding vertices. In applications in clustering, cartography, and visualization, nearby vertices and edges are often bundled to a common node or arc, due to data compression or low resolution. This raises the computational problem of deciding whether a given map φ:G→M comes from an embedding. A map φ:G→M is a weak embedding if it can be perturbed into an embedding ψ_ε:G→M with ∥φ-ψ_ε∥<ε for every ε>0.
    A polynomial-time algorithm for recognizing weak embeddings was recently found by Fulek and Kynčl (2017): It reduces to solving a system of linear equations over Z₂, and it runs in O(n^2ω)≤O(n^4.75) time, where ω<2.373 is the matrix multiplication exponent and n is the number of vertices and edges of G. We improve the running time to O(n log n). Our algorithm is also conceptually simpler: We perform a sequence of local operations that gradually ``untangles'' the image φ(G) into an embedding ψ(G), or reports that φ is not a weak embedding. It generalizes a recent technique developed for the case that G is a cycle and the embedding is a simple polygon, and combines local constraints on the orientation of subgraphs directly, thereby eliminating the need for solving large systems of linear equations.


• Gap-planar graphs,
  • Sang Won Bae, Jean-Francois Baffier, Jinhee Chun, Peter Eades, Kord Eickmeyer, Luca Grilli, Seok-Hee Hong, Matias Korman, Fabrizio Montecchiani, Ignaz Rutter, and Csaba D. Tóth,
  • in Proc. 25th Symposium on Graph Drawing & Network Visualization (Boston, MA, 2017), LNCS 10692, Springer, 531-545.
  • Theoretical Computer Science 745 (2018), 36-52.
  • (abstract) We introduce the family of k-gap-planar graphs, i.e., graphs that have a drawing in which each crossing is assigned to one of the two involved edges and each edge is assigned with at most k≥0 of its crossings. This definition finds motivation in edge casing, as a k-gap-planar graph can be drawn crossing-free after introducing at most k local gaps per edge. We obtain results on the maximum density, drawability of complete graphs, complexity of the recognition problem, and relationships with other families of beyond-planar graphs.


• Online unit clustering in higher dimensions,
  • Adrian Dumitrescu and Csaba D. Tóth,
  • in Proc. 15th Workshop on Approximation and Online Algorithms (Vienna, 2017), LNCS 10787, Springer, pp. 238-252.
  • Algorithmica 84 (5) (2022), 1213-1231.
  • (abstract) We revisit the online Unit Clustering problem in higher dimensions: Given a set of n points in R^d, that arrive one by one, partition the points into clusters (subsets) of diameter at most one, so as to minimize the number of clusters used. In this paper, we work in R^d using the L_∞ norm. We show that the competitive ratio of any algorithm (deterministic or randomized) for this problem must depend on the dimension d. This resolves an open problem raised by Epstein and van Stee (WAOA 2008). We also give a randomized online algorithm with competitive ratio O(d²) for Unit Clustering of integer points (i.e., points in Z^d, d∈N, under L_∞ norm). We complement these results with some additional lower bounds for related problems in higher dimensions.


• A problem on track runners,
  • Adrian Dumitrescu and Csaba D. Tóth,
  • in Proc. 29th Canadian Conference on Computational Geometry (Ottawa, ON, 2017), pp. 198-201.
  • Computational Geometry: Theory and Applications 88 (2020), 101611.
  • (abstract) Consider the unit circle C and a circular arc A of length l=|A|<1. It is shown that there exists k=k(l)∈N, and a schedule for k runners with k distinct but constant speeds so that at any time t ≥ 0, at least one of the k runners is not in A.


• Minimum weight connectivity augmentation for planar straight-line graphs,
  • Hugo A. Akitaya, Rajasekhar Inkulu, Torrie L. Nichols, Diane L. Souvaine, Csaba D. Tóth, and Charles R. Winston,
  • preliminary results in Abstracts of the 26th Fall Workshop on Computational Geometry (New York, NY, 2016);
  • in Proc. 11th International Conference and Workshops on Algorithms and Computation (Hsinchu, 2017), LNCS 10167, Springer, pp. 204-216.
    
  • Theoretical Computer Science 789 (2019), 50-63.
  • (abstract) We consider edge insertion and deletion operations that increase the connectivity of a given planar straight-line graph (PSLG), while minimizing the total edge length of the output. We show that every connected PSLG G=(V,E) in general position can be augmented to a 2-connected PSLG (V,E∪E⁺) by adding new edges of total Euclidean length ‖E⁺‖≤2‖E‖, and this bound is the best possible. An optimal edge set E⁺ can be computed in O(|V|⁴) time; however the problem becomes NP-hard when G is disconnected. Further, there is a sequence of edge insertions and deletions that transforms a connected PSLG G=(V,E) into a planar straight-line cycle G′=(V,E′) such that ‖E′‖≤2‖MST(V)‖, and the graph remains connected with edge length below ‖E‖+‖MST(V)‖ at all stages. These bounds are the best possible.


• Reconstruction of weakly simple polygons from their edges,
  • Hugo A. Akitaya and Csaba D. Tóth,
  • in Proc. 27th International Symposium on Algorithms and Computation (Sydney, 2016), LIPIcs 64, Schloss Dagstuhl, article 10.
  • Internat. J. Comput. Geom. Appl. 28 (2) (2018) 161-180.
  • (abstract) Given m line segments in the plane, do they form the edge set of a weakly simple polygon; that is, can the segment endpoints be perturbed by at most ε, for any ε>0, to obtain a simple polygon? While the analogous question for simple polygons can easily be answered in O(mlog m) time, we show that it is NP-complete for weakly simple polygons. We give O(m)-time algorithms in two special cases: when all segments are collinear, or the segment endpoints are in general position. These results extend to the variant in which the segments are directed, and the counterclockwise traversal of a polygon should follow the orientation.
    We study relaxations of the problem when the union of the m input segments is connected. (i) If each segment can be subdivided into several segments, find the minimum number of subdivision points to form a weakly simple polygon. (ii) If new line segments can be added, find the minimum total length of new segments that create a weakly simple polygon. We give worst-case upper and lower bounds for both problems.


• Multi-colored spanning graphs,
  • Hugo A. Akitaya, Maarten Löffler, and Csaba D. Tóth,
  • in Proc. 24th Symposium on Graph Drawing and Network Visualization (Athens, 2016), LNCS 9801, Springer, pp. 81-93.
  • Theoretical Computer Science 833 (2020), 11-25.
  • (abstract) We study a problem proposed by Hurtado et al. (2016) motivated by sparse set visualization. Given n points in the plane, each labeled with one or more primary colors, a colored spanning graph (CSG) is a graph such that for each primary color, the set of vertices of that color induce connected subgraph. The Min-CSG}problem asks for the minimum sum of edge length in a colored spanning graph. We show that the problem is NP-hard for k primary colors when k≥3 and provide a (2-(1/(3+2ρ)))-approximation algorithm for k=3 that runs in polynomial time, where ρ is the Steiner ratio. Further, we give a O(n) time algorithm in the special case that the input points are collinear and k is constant.


• Constant-factor approximation for TSP with disks,
  • Adrian Dumitrescu and Csaba D. Tóth,
  • in Journey Through Discrete Mathematics: A Tribute to Jiří Matoušek, Springer, 2017, pp. 375-390.
  • (abstract) We revisit the traveling salesman problem with neighborhoods (TSPN) and present the first constant-ratio approximation for disks in the plane: Given a set of n disks in the plane, a TSP tour whose length is at most O(1) times the optimal with high probability can be computed in time that is polynomial in n. Our result is the first constant-ratio approximation for a class of planar convex bodies of arbitrary size and arbitrarily overlaps. In order to achieve a O(1)-approximation, we reduce the traveling salesman problem with disks, up to constant factors, to a minimum weight hitting set problem in a geometric hypergraph. The connection between TSPN and hitting sets in geometric hypergraphs, established here, is likely to have future applications.


• Monotone paths in geometric triangulations,
  • Adrian Dumitrescu, Ritankar Mandal, and Csaba D. Tóth,
  • in Proc. 27th International Workshop on Combinatorial Algorithms (Helsinki, 2016), LNCS 9843, Springer, pp. 411-422.
  • Theory of Computing Systems 62 (6) (2018), 1490-1524.
  • (abstract) We prove that the (maximum) number of monotone paths in a triangulation of n points in the plane is O(1.8026ⁿ). This improves an earlier upper bound of O(1.8393ⁿ) established by Löffler et al. (2013). The current best lower bound of Ω(1.7034ⁿ) is due to the same authors. Given a planar straight-line graph G with n vertices, we show that the number of monotone paths in G can be computed in O(n²) time.


• A note on independent hyperplanes and general position subsets in d-space,
  • Jean Cardinal, Csaba D. Tóth, and David R. Wood,
  • Journal of Geometry 108 (1) (2017), 33-43.


• Recognizing weakly simple polygons,
  • Hugo A. Akitaya, Greg Aloupis, Jeff Erickson, and Csaba D. Tóth,
  • in Proc. 32nd Symposium on Computational Geometry (Boston, MA, 2016), LIPIcs 51, article 8.
  • Discrete and Computational Geometry 58 (4) (2017), 785–821.
  • (abstract) We present an O(n log n)-time algorithm that determines whether a given planar n-gon is weakly simple. This improves upon an O(n² log n)-time algorithm by Chang, Erickson, and Xu (2015). Weakly simple polygons are required as input for several geometric algorithms. As such, how to recognize simple or weakly simple polygons is a fundamental question.


• Anchored rectangle and square packings,
  • Kevin Balas, Adrian Dumitrescu, and Csaba D. Tóth,
  • in Proc. 32nd Symposium on Computational Geometry (Boston, MA, 2016), LIPIcs 51, article 13.
  • Discrete Optimization 26 (2017), 131-162.
  • (abstract) For points p₁,...,p_n in the unit square [0,1]², an anchored rectangle packing consists of interior-disjoint axis-aligned empty rectangles r₁,...,r_n ⊂ [0,1]² such that point p_i is a corner of the rectangle r_i (that is, r_i is anchored at p_i) for i=1,...,n. We show that for every set of n points in [0,1]², there is an anchored rectangle packing of area at least 7/12-O(1/n), and for every n∈N, there are n-element point sets for which the area of every anchored rectangle packing is at most 2/3. If the rectangles are required to be squares, we show that the maximum area of an anchored square packing is always at least 9/47 and sometimes at most 7/27.


• The planar tree packing theorem,
  • Markus Geyer, Michael Hoffmann, Michael Kaufmann, Vincent Kusters, and Csaba D. Tóth,
  • in Proc. 32nd Symposium on Computational Geometry (Boston, MA, 2016), LIPIcs 51, article 41.
  • J. Comput. Geom. 8 (2) (2017), 109–177.
  • (abstract) Packing graphs is a combinatorial problem where several given graphs are being mapped into a common host graph such that every edge is used at most once. Much research has been devoted to the packing of trees, and especially to the case where the host graph is planar. In the planar tree packing problem we are given two trees T₁ and T₂ on n vertices and have to find a planar graph on n vertices that is the edge-disjoint union of T₁ and T₁. A clear exception that must be made is the star which cannot be packed together with any other tree. But according to a conjecture of García et al. from 1997 this is the only exception, and all other pairs of trees admit a planar packing. Previous results addressed various special cases, such as a tree and a spider tree, a tree and a caterpillar, two trees of diameter four, two isomorphic trees, and trees of maximum degree three. Here we settle the conjecture in the affirmative and prove its general form, thus making it the planar tree packing theorem. The proof is constructive and provides a polynomial time algorithm to obtain a packing for two given non-star trees.


• Note on k-planar crossing numbers,
  • János Pach, László Székely, Csaba D. Tóth, and Géza Tóth,
  • Computational Geometry: Theory and Applications 68 (2018), 2-6.
  • (abstract) The crossing number cr(G) of a graph G=(V,E) is the smallest number of edge crossings over all drawings of G in the plane. For any k≥ 1, the k-planar crossing number of G, cr_k(G), is defined as the minimum of cr(G₀)+cr(G₁)+...+cr(G_k-1) over all graphs G₀, G₁,...,G_k-1 with G=G₀∪G₁∪...∪G_k-1. It is shown that for every k≥1, we have cr_k(G)≤ ((2/k²)-(1/k³))cr(G). This bound does not remain true if we replace the constant ((2/k²)-(1/k³)) by any number smaller than 2/k². Some of the results extend to the rectilinear variants of the k-planar crossing number.


• Linear-size universal point sets for one-bend drawings,
  • Maarten Löffler and Csaba D. Tóth,
  • in Proc. 23rd Symposium on Graph Drawing and Network Visualization (Los Angeles, CA, 2015), LNCS 9411, Springer, pp. 423-429.
  • (abstract) For every integer n≥ 4, we construct a planar point set S_n of size 6n-10 such that every n-vertex planar graph admits a plane embedding in which the vertices are mapped to points in S_n, and every edge is either a line segment or a polyline with one bend, where the bend point is also in S_n.


• Realization of simply connected polygonal linkages and recognition of unit disk contact trees,
  • Clinton Bowen, Stephane Durocher, Maarten Löffler, Anika Rounds, André Schulz, and Csaba D. Tóth,
  • in Proc. 23rd Symposium on Graph Drawing and Network Visualization (Los Angeles, CA, 2015), LNCS 9411, Springer, pp. 447-459.
  • (abstract) We wish to decide whether a simply connected flexible polygonal structure can be realized in Euclidean space. Two models are considered: polygonal linkages (body-and-joint framework) and contact graphs of unit disks in the plane. (1) We show that it is strongly NP-hard to decide whether a given polygonal linkage is realizable in the plane when the bodies are convex polygons and their contact graph is a tree; the problem is weakly NP-hard already for a chain of rectangles. (2) We also show that it is strongly NP-hard to decide whether a given tree is the contact graph of interior-disjoint unit disks in the plane.


• On the number of anchored rectangle packings for a planar point set,
  • Kevin Balas and Csaba D. Tóth,
  • in Proc. 21st Computing and Combinatorics Conference (Beijing, 2015), LNCS 9198, Springer, 2015, pp. 377-389.
  • Theoretical Computer Science 654 (2016), 143–154.
  • (abstract) We consider packing axis-aligned rectangles r₁,... , r_n in the unit square [0,1]² such that a vertex of each rectangle r_i is a given point p_i (i.e., r_i is anchored at p_i); and explore the combinatorial structure of all locally maximal configurations. When the given points are lower-left corners of the rectangles, then the number of maximal packings is shown to be at most 2ⁿC_n, where C_n is the nth Catalan number. The number of maximal packings remains exponential in n when the points may be arbitrary corners of the rectangles. Our upper bounds are complemented with exponential lower bounds.


• Convex polygons in geometric triangulations,
  • Adrian Dumitrescu and Csaba D. Tóth,
  • in Proc. WADS (Victoria, BC, 2015), LNCS 9214, Springer, 2015, pp. 289-300.
  • Combinatorics, Probability, and Computing 26 (5) (2017), 641-659.
  • (abstract) We show that the maximum number of convex polygons in a triangulation of n points in the plane is O(1.5029ⁿ). This improves an earlier bound of O(1.6181ⁿ) established by van Kreveld, Löffler, and Pach (2012) and almost matches the current best lower bound of Ω(1.5028ⁿ) due to the same authors. Given a planar straight-line graph G with n vertices, we show how to compute efficiently the number of convex polygons in G.


• Binary Space Partitions,
  • Adrian Dumitrescu and Csaba D. Tóth,
  • in Encyclopedia of Algorithms (Ming-Yang Kao, ed.), 2nd edition, 2015, Springer.


• Arc diagrams, flip distances, and Hamiltonian triangulations,
  • Jean Cardinal, Michael Hoffmann, Vincent Kusters, Csaba D. Tóth, and Manuel Wettstein,
  • in Proc. 32nd Sympos. Theoretical Aspects of Computer Science (Munich, 2015), LIPIcs 30, pp. 197-210.
  • Computational Geometry: Theory and Applications 68 (2018), 206-225.
  • (abstract) We show that every triangulation (maximal planar graph) on n≥ 6 vertices can be flipped into a Hamiltonian triangulation using a sequence of less than n/2 combinatorial edge flips. The previously best upper bound uses 4-connectivity as a means to establish Hamiltonicity. But in general about 3n/5 flips are necessary to reach a 4-connected triangulation. Our result improves the upper bound on the diameter of the combinatorial flip graph of triangulations on n vertices from 5.2n-33.6 to 5n-23. We also show that for every triangulation on n vertices there is a simultaneous flip of less than 2n/3 edges to a 4-connected triangulation. The bound on the number of edges is tight, up to an additive constant. As another application we show that every planar graph on n vertices admits an arc diagram with less than n/2 biarcs, that is, after subdividing less than n/2 (of potentially 3n-6) edges the resulting graph admits a 2-page book embedding.


• Disjoint edges in topological graphs and the tangled-thrackle conjecture,
  • Andres J. Ruiz-Vargas, Andrew Suk, and Csaba D. Tóth
  • in Proc. 22nd Sympos. Graph Drawing (Würzburg, 2014), LNCS 8871, Springer, pp. 284-293.
  • European J. Combinatorics 51 (2016), 398–406.


• On fence patrolling by mobile agents,
  • Adrian Dumitrescu, Anirban Ghosh, and Csaba D. Tóth,
  • preliminary version in Proc. 25th Canadian Conference on Computational Geometry (Waterloo, ON, 2013).
  • Electronic Journal of Combinatorics 21 (3) (2014), P3.4.
  • (abstract) Suppose that a fence needs to be protected (perpetually) by k mobile agents with maximum speeds v₁,...,v_k so that no point on the fence is left unattended for more than a given amount of time. The problem is to determine if this requirement can be met, and if so, to design a suitable patrolling schedule for the agents. Alternatively, one would like to find a schedule that minimizes the idle time, that is, the longest time interval during which some point is not visited by any agent. We revisit this problem, introduced by Czyzowicz et al. (2011), and discuss several strategies for the cases where the fence is an open and a closed curve, respectively.
    In particular: (i) we disprove a conjecture by Czyzowicz et al. regarding the optimality of their Algorithm A₂ for unidirectional patrolling of a closed fence; (ii) we present an algorithm with a lower idle time for patrolling an open fence, improving an earlier result of Kawamura and Kobayashi.


• Covering grids by trees,
  • Adrian Dumitrescu and Csaba D. Tóth,
  • in Proc. 26th Canadian Conference on Computational Geometry (Halifax, NS, 2014).
  • (abstract) Given n points in the plane, a covering tree is a tree whose edges are line segments that jointly cover all the points. Let G^d_n be a n ×... × n grid in Z^d. It is known that G³_n can be covered by an axis-aligned polygonal path with (3/2)n²+O(n) edges, thus in particular by a polygonal tree with that many edges. Here we show that every covering tree for the n³ points of G³_n has at least (1+c₃)n² edges, for some constant c₃>0. On the other hand, there exists a covering tree for the n³ points of G³_n consisting of only n²+n+1 line segments, where each segment is either a single edge or a sequence of collinear edges. Extensions of these problems to higher dimensional grids (i.e., G^d_nfor d ≥ 3) are also examined.


• The Szemerédi-Trotter Theorem in the complex plane,
  • Csaba D. Tóth,
  • Combinatorica 35 (1) (2015), 95-126.


• Computing opaque interior barriers à la Shermer,
  • Adrian Dumitrescu, Minghui Jiang, and Csaba D. Tóth,
  • in Proc. 17th APPROX (Barcelona, 2014), LIPIcs 28, Dagstuhl, pp. 128-143.
  • SIAM Journal on Discrete Mathematics 29 (3) (2015), 1372–1386.
  • (abstract) The problem of finding a collection of curves of minimum total length that meet all the lines intersecting a given polygon was initiated by Mazurkiewicz in 1916. Such a collection forms an opaque barrier for the polygon. In 1991 Shermer proposed an exponential-time algorithm that computes an interior-restricted barrier made of segments for any given convex n-gon. He conjectured that the barrier found by his algorithm is optimal, however this was refuted recently by Provan et al. Here we give a Shermer like algorithm that computes an interior polygonal barrier whose length is at most 1.7168 times the optimal and that runs in O(n) time. As a byproduct, we also deduce upper and lower bounds on the approximation ratio of Shermer's algorithm.


• Diffuse reflection radius in a simple polygon,
  • Eli Fox-Epstein, Csaba D. Tóth, and Andrew Winslow
  • in Proc. 20th Computing and Combinatorics Conference (Atlanta, GA, 2014), LNCS 8591, Springer, pp. 239-250.
  • Algorithmica 76 (4) (2016), 910-931.
  • (abstract) It is shown that every simple polygon with n walls can be illuminated from a single point light source s after at most ⌊(n-2)/4⌋ diffuse reflections, and this bound is the best possible. A point s with this property can be computed in O(n log n) time.


• A census of plane graphs with polyline edges,
  • Andrea Francke and Csaba D. Tóth,
  • in Proc. 30th Sympos. on Computational Geometry (Kyoto, 2014), ACM Press, pp. 242-250.
  • SIAM J. Discrete Math. 31 (2) (2017), 1174-1195.
  • (abstract) It is shown that on every n-element point set in the plane, at most exp(O(kn)) labeled planar graphs can be embedded using polyline edges with k bends per edge. This is the first exponential upper bound for the number of labeled plane graphs where the edges are polylines of constant size. Several standard tools developed for the enumeration of straight-line graphs, such as triangulations and crossing numbers, are unavailable in this scenario. Furthermore, the exponential upper bound does not carry over to other popular relaxations of straight-line edges: for example, the number of plane graphs realizable with x-monotone edges on n points is already super-exponential.


• Free edge lengths in plane graphs,
  • Zachary Abel, Robert Connelly, Sarah Eisenstat, Radoslav Fulek, Filip Morić, Yoshio Okamoto, Tibor Szabó, and Csaba D. Tóth,
  • in Proc. 30th Sympos. on Computational Geometry (Kyoto, 2014), ACM Press, pp. 426-435.
  • Discrete and Computational Geometry 54 (1) (2015), 259-289.
  • (abstract) We study straight-line embeddings of planar graphs subject to metric constraints. A planar graph G is free in a planar ``host'' graph H, G⊆H, if the edges if G have arbitrary positive lengths, that is, for any choice of positive lengths for the edges of G, the host H has a straight-line embedding that realizes these lengths. A planar graph G is extrinsically free in H, G⊆H, if any constraint on the edge lengths of G depends on G alone, irrespective of any additional edges of the host H. We characterize all planar graphs G that are free in every host H, G⊆H, and all the planar graphs G that are extrinsically free in every host H, G⊆H. The case of cycles G=C<sub>k</sub> provides a new version of the celebrated carpenter's rule problem. Even though cycles C<sub>k</sub>, k ≥ 4, are not extrinsically free in all triangulations, it turns out that ``nondegenerate'' edge lengths are always realizable, where the edge lengths are considered degenerate if the cycle can be flattened (into a line) in two different ways. Separating triangles, and separating cycles in general, play an important role in our arguments. We show that every star is free in a 4-connected triangulation (which has no separating triangle).


• The flip diameter of rectangulations and convex subdivisions,
  • Eyal Ackerman, Michelle M. Allen, Gill Barequet, Maarten Löffler, Joshua Mermelstein, Diane L. Souvaine, and Csaba D. Tóth,
  • in Proc. Latin American Theoretical INformatics (Montevideo, 2014), LNCS 8392, Springer, 2014, pp. 478-489.
  • Discrete Mathematics and Theoretical Computer Science 18 (3) (2016), article 4.
  • (abstract) We study the configuration space of rectanulations and convex subdivisions of n points in the plane. It is shown that a sequence of O(n log n) elementary flip and rotate operations can transform any rectangulation to any other rectangulation on the same set of n points. This bound is the best possible for some point sets, while Θ(n) operations are sufficient and necessary for others. Some of our bounds generalize to convex subdivisions of n points in the plane.


• On the upward planarity of mixed plane graphs,
  • Fabrizio Frati, Michael Kaufmann, János Pach, Csaba D. Tóth, and David Wood,
  • in Proc. 21st Symposium on Graph Drawing (Bordeaux, 2013), LNCS 8242, Springer, pp 1-12.
  • J. Graph Algorithms and Applications 18 (2) (2014), 253-279.
  • (abstract) A mixed plane graph is a plane graph whose edge set is partitioned into a set of directed edges and a set of undirected edges. An orientation of a mixed plane graph G is an assignment of directions to the undirected edges of G resulting in a directed plane graph G'. In this paper, we study the computational complexity of testing whether a given mixed plane graph G is upward planar, i.e., whether it admits an orientation resulting in a directed plane graph G' such that G' admits a planar drawing in which each edge is represented by a curve monotonically increasing in the y-direction according to its orientation. Our contribution is threefold. First, we show that the upward planarity testing problem is solvable in cubic time for mixed outerplane graphs. Second, we show that the problem of testing the upward planarity of mixed plane graphs reduces in quadratic time to the problem of testing the upward planarity of mixed plane triangulations. Third, we exhibit linear-time testing algorithms for two classes of mixed plane triangulations, namely mixed plane 3-trees and mixed plane triangulations in which the undirected edges induce a forest.


• On the total perimeter of homothetic convex bodies in a convex container,
  
  • Adrian Dumitrescu and Csaba D. Tóth,
  • preliminary version: "Packing disks that touch the boundary of a square" in Abstracts of 22nd Fall Workshop on Computational Geometry (College Park, MD, 2012).
  • in Proc. 16th APPROX (Berkeley, CA, 2013), LNCS 8096, Springer, pp. 96-109.
  • Contributions to Algebra and Geometry 56 (2) (2015), 515-532.
  • (abstract) For two convex bodies, C and D, consider a packing S of n positive homothets of C contained in D. We estimate the total perimeter of the bodies in S, denoted per(S), in terms of n. When all homothets of C touch the boundary of the container D, we show that either per(S)=O(log n) or per(S)=O(1), depending on how C and D "fit together,"' and these bounds are the best possible apart from the constant factors. Specifically, we establish an optimal bound per(S)=O(log n) unless D is a convex polygon and every side of D is parallel to a corresponding segment on the boundary of C (for short, D is parallel to C). When D is parallel to C but the homothets of C may lie anywhere in D, we show that per(S)=O((1+esc(S)) log n/log log n), where esc(S) denotes the total distance of the bodies in S from the boundary of D. Apart from the constant factor, this bound is also the best possible.


• Geometric biplane graphs II: Graph augmentation,
  • Alfredo García, Ferran Hurtado, Matias Korman, Inês Matos, Maria Saumell, Rodrigo I. Silveira, Javier Tejel, and Csaba D. Tóth,
  • in Proc. Mexican Conf. on Discrete Math. and Computational Geometry (Oaxaca, 2013).
  • Graphs and Combinatorics 31 (2) (2015), 427-452.
  • (abstract) We study biplane graphs drawn on a finite point set S in the plane in general position. This is the family of geometric graphs whose vertex set is S and can be decomposed into two plane graphs. We show that every sufficiently large point set admits a 5-connected biplane graph and that there are arbitrarily large point sets that do not admit any 6-connected biplane graph. Furthermore, we show that every plane graph (other than the wheel or the fan) can be augmented into a 4-connected biplane graph. However, there are arbitrarily large plane graphs that cannot be augmented to a 5-connected biplane graph by adding pairwise noncrossing edges.


• Geometric biplane graphs I: Maximal graphs,
  • Alfredo García, Ferran Hurtado, Matias Korman, Inês Matos, Maria Saumell, Rodrigo I. Silveira, Javier Tejel, and Csaba D. Tóth,
  • in Proc. Mexican Conf. on Discrete Math. and Computational Geometry (Oaxaca, 2013).
  • Graphs and Combinatorics 31 (2) (2015), 407-425.
  • (abstract) We study biplane graphs drawn on a finite point set S in the plane in general position. This is the family of geometric graphs whose vertex set is S and can be decomposed into two plane graphs. We show that two maximal biplane graphs in the sense that no edge can be added while staying biplane may differ in the number of edges, and we provide an efficient algorithm for adding edges to a biplane graph to make it maximal. We also study extremal properties of maximal biplane graphs such as the maximum number of edges and the largest maximum connectivity over n-element point sets.


• Counting carambolas,
  • Maarten Löffler, André Schulz, and Csaba D. Tóth,
  • in Proc. 25th Canadian Conf. on Comput. Geom. (Waterloo, ON, 2013), pp. 163-168.
  • Graphs and Combinatorics 32 (3) (2016), 923-942.
  • (abstract) We give upper and lower bounds on the maximum and minimum number of certain geometric configurations hidden in a triangulation of n points in the plane. Configurations of interest include star-shaped polygons and monotone paths. We also consider related problems in directed planar straight-line graphs.


• A tight bound for point guards in piece-wise convex art galleries,
  • Javiér Cano, Csaba D. Tóth, and Jorge Urrutia,
  • in Abstracts of the 19th Fall Workshop on Comput. Geom. (Medford, MA, 2009), pp. 43-44.
  • Comput. Geom. Theory Appl. 46 (8) (2013), 945–958.


• Planar packing of binary trees,
  
  • Markus Geyer, Michael Kaufmann, Michael Hoffmann, Vincent Kusters, Csaba D. Tóth,
  • in Proc. WADS (London, ON, 2013), LNCS 8037, Springer, pp. 353–364.


• Universal point sets for planar three-trees,
  • Radoslav Fulek and Csaba D. Tóth,
  • preliminary version in Proc. WADS (London, ON, 2013), LNCS 8037, Springer, pp. 341–352.
  • Journal of Discrete Algorithms 30 (2015), 101-112.
  • (abstract) For every positive integer n, we present a set S_n of O(n^3/2log n) points in the plane such that every planar 3-tree with n vertices has a straight-line embedding in the plane in which the vertices are mapped to a subset of S_n. This is the first subquadratic upper bound on the size of universal point sets for planar 3-trees, as well as for the class of 2-trees and serial parallel graphs.


• Vertex-colored encompassing graphs,
  • Michael Hoffmann and Csaba D. Tóth,
  • Graphs and Combinatorics 30 (4) (2014), 933-947.


• Diffuse reflections in simple polygons,
  
  • Gill Barequet, Sarah M. Cannon, Eli Fox-Epstein, Benjamin Hescott, Diane L. Souvaine, Csaba D. Tóth, and Andrew Winslow,
  • in Proc. VII Latin-American Algorithms, Graphs and Optimization Symposium (Playa del Carmen, 2013), Electronic Notes in Discrete Mathematics 44 (5) (2013), 345–350.
  • Discrete Applied Mathematics 210 (2016), 123-132.
  • (abstract) We prove a conjecture of Aanjaneya et al. that the maximum number of diffuse reflections needed for a point light source to illuminate the interior of simple polygon with n walls is floor(n/2)-1. Light reflecting diffusely leaves a surface in all directions, rather than at an identical angle as with specular reflections.


• The traveling salesman problem for lines, balls and planes,
  • Adrian Dumitrescu and Csaba D. Tóth,
  • in Proc. 24th ACM-SIAM Symposium on Discrete Algorithms (New Orleans, LA, 2013), SIAM, pp. 828-843.
  • Transactions on Algorithms 12 (3) (2016), article 43.
  • (abstract) We revisit the traveling salesman problem with neighborhoods (TSPN) and obtain several approximation algorithms. These constitute either improvements over previously best approximations achievable in comparable times (for unit disks in the plane), or first approximations ever (for planes, lines and unit balls in 3-space).
    (I) Given a set of n planes in 3-space, a TSP tour that is at most 2.31 times longer than the optimal can be computed in O(n) time.
    (II) Given a set of n lines in 3-space, a TSP tour that is at most O(log³n) times longer than the optimal can be computed in polynomial time.
    (III) Given a set of n unit disks in the plane (resp., unit balls in 3-space), we improve the approximation ratio using a black box that computes an approximate tour for a set of points (the centers of a subset of disks).


• Covering paths for planar point sets,
  • Adrian Dumitrescu, Dániel Gerbner, Balázs Keszegh, Csaba D. Tóth,
  • preliminary version in Proc. 20th Symposium on Graph Drawing (Redmond, WA, 2012), LNCS 7704, Springer, 2013, pp. 303–314.
  • Proc. 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications (Veszprém, 2013).
  • Discrete Comput. Geom. 51 (2) (2014), 462-484.
  • (abstract) Given a set of points, a covering path is a directed polygonal path that visits all the points. If no three points are collinear, every covering path requires at least n/2 segments, and n-1 straight line segments obviously suffice even if the covering path is required to be noncrossing. We show that for any n points in the plane, there exists a (possibly self-crossing) covering path consisting of n/2 +O(n/log n) straight line segments. If the path is required to be noncrossing, we prove that (1-ε)n straight line segments suffice for a small constant ε>0, and we exhibit n-element point sets that require at least 5n/9 -O(1) segments in any such path. Further, we show that computing a non-crossing covering path for n points in the plane requires Ω(n log n) time in the worst case.


• Edge guards for polyhedra in three-space,
  • Javiér Cano, Csaba D. Tóth, Jorge Urrutia, and Giovanni Viglietta,
  • Computational Geometry: Theory and Applications 104 (2022), 101859.
  • Preliminary version in Proc. 24th Canadian Conf. Comput. Geom. (Charlottetown, PE, 2012), pp. 155-160.


• Crossing angles of geometric graphs,
  • Karin Arikushi and Csaba D. Tóth,
  • in Proc. 6th Conference on Combinatorial Optimization and Applications (Banff, AB, 2012), LNCS 7402, Springer, pp. 103-114.
  • J. Graph Algorithms and Applications 18 (3) (2014), 401-420.
  • (abstract) The crossing angle number of a graph G, denoted can(G) is the minimum number of angles between crossing edges in a straight line drawing of G. It is shown that an n-vertex graph G with can(G) = O(1) has O(n) edges, but there are bounded degree graphs G with arbitrarily large can(G). There are bounded degree graphs G = (V,E) such that for any two straight-line drawings of G with the same prescribed crossing angles, there is a subset U of V, of vertices of size |U|≥|V|/2 whose two drawings are similar.


• Monotone paths in convex subdivisions and polytopes,
  • Adrian Dumitrescu, Günter Rote, and Csaba D. Tóth,
  • preliminary results in Abstracts of the 21st Fall Workshop on Comput. Geom. (New York, NY, 2011).
  • in Proc. 18th Computing and Combinatorics Conference (Sydney, 2012), LNCS 7434, Springer, pp. 240?251.
  • in Discrete Geometry and Optimization, vol 69 of Fields Institute Communications, 2013, Springer, pp. 79-104.
  • (abstract) It is shown that for every subdivision of the plane into n convex faces, exactly k of which are unbounded, there is a monotone polygonal path on the boundaries of the faces that consists of at least Ω(log (n/k)/log log (n/k)) segments, and this bound is the best possible.


• Minimum convex partitions and maximum empty polytopes,
  • Adrian Dumitrescu, Sariel Har-Peled, and Csaba D. Tóth,
  • in Proc. 13th Scandinavian Symposium and Workshops on Algorithm Theory (Helsinki, 2012), LNCS 7357, Springer, pp. 213-224.
  • Journal of Computational Geometry 5 (1) (2014), 86–103.


• Conflict-free graph orientations with parity constraints,
  • Sarah Cannon, Mashhood Ishaque, and Csaba D. Tóth,
  • preliminary results "Even orientations with forbidden pairs and demands" in the Abstracts of the 20th Fall Workshop on Comput. Geom. (Stony Brook, NY, 2010).
  • in Proc. 6th Conf. on Fun with Algorithms (Venice, 2012), LNCS 7288, Springer, pp. 57-68.
  • (abstract) It is known that every multigraph with an even number of edges has an even orientation (i.e., all indegrees are even). We study parity constrained graph orientations under additional constraints. We consider three types of constraints for a multigraph G=(V,E): (1) an exact conflict is an edge set C⊆ E and a vertex v∈ V such that C should not equal the set of incoming edges at v; (2) a subset conflictis an edge set C⊆ E and a vertex v∈ V such that C should not be a subset of incoming edges at v; (3) a vertex demand f(v),v∈ V, is a minimum indegree for v. We show that it is NP-complete to decide whether $G$ has an even orientation with exact or subset conflicts, for all conflict sets of size two or higher. We present efficient algorithms for computing parity constrained orientations with disjoint exact or subset conflict pairs and with demands.


• Packing anchored rectangles,
  • Adrian Dumitrescu and Csaba D. Tóth,
  • in Proc. 23rd ACM-SIAM Sympos. on Discrete Algorithms (Kyoto, 2012), SIAM, 2012, pp. 294-305.
  • Combinatorica 35 (1) (2015), 39-61.
  • (abstract) Let S be a set of n points in the unit square [0,1]², one of which is the origin. We construct n pairwise interior-disjoint axis-aligned empty rectangles such that the lower-left corner of each rectangle is a point in S, and the rectangles jointly cover at least a positive constant area. This is a first step towards the solution of a longstanding conjecture that the rectangles in such a packing can jointly cover an area of at least 1/2.


• Plane geometric graph augmentation: a generic perspective,
  • Ferran Hurtado and Csaba D. Tóth,
  • in Thirty Essays on Geometric Graph Theory (J. Pach, ed.), Springer, 2013, pp. 327-354.
  • (abstract) Graph augmentation problems are motivated by network design, and have been studied ex- tensively in optimization. We consider augmentation problems over plane geometric graphs, that is, graphs given with a crossing-free straight-line embedding in the plane. The geomet- ric constraints on the possible new edges render some of the simplest augmentation problems intractable, and in many cases only extremal results are known. We survey recent results, highlight common trends, and gather numerous conjectures and open problems.


• Constrained tri-connected planar straight line graphs,
  • Marwan Al-Jubeh, Gill Barequet, Mashhood Ishaque, Diane L. Souvaine, Csaba D. Tóth, and Andrew Winslow,
  • preliminary results in Abstracts of the 20th Fall Workshop on Comput. Geom. (Stony Brook, NY, 2010).
  • preliminary results "Connecting obstacles in vertex-disjoint paths" in Abstracts of the 26th European Workshop Comput. Geom. (Dortmund, 2010).
  • in Thirty Essays on Geometric Graph Theory (J. Pach, ed.), Springer, 2013, pp. 49-70.


• Upper bound constructions for untangling planar geometric graphs,
  • Javier Cano, Csaba D. Tóth, and Jorge Urrutia,
  • in Proc. 19th Sympos. Graph Drawing (Eindhoven, 2011), LNCS 7034, Springer, pp. 290-295.
  • SIAM J. Discrete Math. 28 (4) (2014), 1935-1943.
  • (abstract) For every positive integer n, there is a straight-line drawing D_n of a planar graph on n vertices such that in any crossing-free straight-line drawing of the graph, at most O(n^0.4982) vertices lie at the same position as in D_n. This improves on an earlier bound of O(√n) by Goaoc et al..


• Open guard edges and edge guards in simple polygons,
  • Csaba D. Tóth, Godfried Toussaint, and Andrew Winslow,
  • in Proc. 23rd Canadian Conf. Comput. Geom. (Toronto, ON, 2011), pp. 449-454.
  • in Computational Geometry (A. Marquez et al., eds.), LNCS 7579, Springer, 2012, pp. 54-64.
  • (abstract) An open edge of a simple polygon is the set of points in the relative interior of an edge. We revisit several art gallery problems, previously considered for closed edge guards, using open edge guards. A guard edge of a polygon is an edge that sees every point inside the polygon. We show that every simple non-starshaped polygon admits at most one open guard edge, and give a simple new proof that it admits at most three closed guard edges. We characterize open guard edges, and derive an algorithm that finds all open guard edges of a simple n-gon in O(n) time in the RAM model of computation. Finally, we present lower bound constructions for simple polygons with n vertices that require [n/3] open edge guards, and conjecture that this bound is tight.


• Collinearities in kinetic points,
  • Ben D. Lund, George B. Purdy, Justin W. Smith, and Csaba D. Tóth,
  • in Proc. 23rd Canadian Conf. Comput. Geom. (Toronto, ON, 2011), pp. 223-227.


• Simultaneously flippable edges in triangulations,
  • Diane L. Souvaine, Csaba D. Tóth, and Andrew Winslow,
  • in Proc. XIV Spanish Meeting on Comput. Geom. (Alcalá de Henares, 2011), pp. 137-140.
  • in Computational Geometry (A. Marquez et al., eds.), LNCS 7579, Springer, 2012, pp. 138-145.
  • (abstract) We show that every straight-line triangulation on n vertices contains at least (n - 4)/5 simultaneously flippable edges. This bound is the best possible, and resolves an open problem by Galtier et al..


• Counting plane graphs: flippability and its applications,
  • Michael Hoffmann, André Schulz, Micha Sharir, Adam Sheffer, Csaba D. Tóth, and Emo Welzl,
  • in Proc. WADS (Brooklyn, NY, 2011), LNCS 6844, Springer, pp. 524-535.
  • in Thirty Essays on Geometric Graph Theory (J. Pach, ed.), Springer, 2013, pp. 303-326.
  • (abstract) We generalize the notions of flippable and simultaneously-flippable edges in a triangulation of a set S of points in the plane, into so called pseudo-simultaneously flippable edges. Such edges are related to the notion of convex decompositions spanned by S. We derive a worst-case tight lower bound on the number of pseudo-simultaneously flippable edges in any triangulation, and use this bound to obtain upper bounds for the maximal number of several types of plane graphs that can be embedded (with crossing-free straight edges) on a fixed set of N points in the plane. More specifically, denoting by tr(N) < 30^N the maximum possible number of triangulations of a set of N points in the plane, we show that every set of N points in the plane can have at most 6.9283^N·tr(N) < 207.85^N plane graphs, O(4.8895^N)·tr(N) = O(146.69^N) spanning trees, and O(5.4723^N)·tr(N) = O(164.17^N) forests (that is, cycle-free graphs). We also obtain upper bounds for the number of crossing-free straight-edge graphs with at most cN edges and for the number of such graphs with at least cN edges.


• Disjoint compatible geometric matchings,
  • Mashhood Ishaque, Diane L. Souvaine, and Csaba D. Tóth,
  • in Proc. 27th Sympos. on Comput. Geom. (Paris, 2011), ACM Press, pp. 125-134.
  • Discrete Comput. Geom.49 (1) (2013), 89-131.
  • (abstract) We prove that for every set of n pairwise disjoint line segments in the plane in general position, there is another set of n segments such that the 2n segments form pairwise disjoint simple polygons in the plane. This settles in the affirmative the Disjoint Compatible Matching Conjecture by Aichholzer et al.. The key tool in our proof is a novel subdivision of the free space around n disjoint line segments into at most n+1 convex cells such that the dual graph of the subdivision contains two edge-disjoint spanning trees.


• Bounds on the maximum multiplicity of some common geometric graphs,
  • Adrian Dumitrescu, André Schulz, Adam Sheffer, and Csaba D. Tóth,
  • in Proc. 28th Sympos. on Theoretical Aspects of Comp. Sci. (Dortmund, 2011), vol. 5 of LIPICS, Schloss Dagstuhl, pp. 637-648.
  • SIAM Discrete Math. 27 (2) (2013), 802–826.


• The union of colorful simplices spanned by a colored point set,
  • André Schulz and Csaba D. Tóth,
  • in Proc. 4th Conf. on Combin. Optimization and Appl. (Kailua Kona, HI, 2010), LNCS 6508, Springer, pp. 324-338.
  • Comput. Geom. Theory Appl. 46 (2013), 574-590.
  • (abstract) A simplex spanned by a colored point set in Euclidean d-space is colorful if all vertices have distinct colors. The union of all full-dimensional colorful simplices spanned by a colored point set is called the colorful union. We show that in every dimension d, the maximum combinatorial complexity of the colorful union of n colored points is between Ω(n^(d-1)2) and O(n^(d-1)2 log n). For d=2, the upper bound is known to be O(n), and for d=3 we present an upper bound of O(n⁴ α(n)), where α(.) is the extremely slowly growing inverse Ackermann function. We also prove several structural properties of the colorful union. In particular, we show that the boundary of the colorful union is covered by O(n^d-1) hyperplanes, and the colorful union is the union of d+1 star-shaped polyhedra. These properties lead to efficient data structures for point inclusion queries in the colorful union.


• Graphs that admit polyline drawings with few crossing angles,
  • Eyal Ackerman, Radoslav Fulek, and Csaba D. Tóth,
  • preliminary version "On the size of graphs that admit polyline drawings with few bends and crossing angles" in Proc. 18th Sympos. on Graph Drawing (Konstanz, 2010), LNCS 6502, Springer, 2011, pp. 1-12.
  • SIAM J. Discrete Math. 26 (1) (2012), 305-320.
  • (abstract) We consider graphs that admit polyline drawings where all crossings occur at the same angle α ∈ (0, π/2]. We prove that every graph on n vertices that admits such a polyline drawing with at most two bends per edge has O(n) edges. This result remains true when each crossing occurs at an angle from a small set of angles. We also provide several extensions that might be of independent interest.


• Watchman tours for polygons with holes,
  • Adrian Dumitrescu and Csaba D. Tóth,
  • in Proc. 22nd Canadian Conf. Comput. Geom. (Winnipeg, MB, 2010), pp. 113-116.
  • Comput. Geom. Theory Appl. 45 (7) (2012), 326-333.
  • (abstract) A watchman tour in a polygonal domain (for short, polygon) is a closed curve such that every point in the polygon is visible from at least one point of the tour. The problem of finding a shortest watchman tour is NP-hard for polygons with holes. We show that the length of a minimum watchman tour in a polygon P with k holes is O(per(P)+ k^1/2 diam(P)), where per(P) and diam(P) denote the perimeter and the diameter of P, respectively. Apart from the multiplicative constant, this bound is tight in the worst case. A watchman tour of this length can be computed in O(n log n) time, where n is the total number of vertices. We generalize our results to watchman tours in polyhedra with holes in 3-space. Our upper bound, O(per(P)+ √k diam(P)per(P) +k^2/3 diam(P)), is again tight in the worst case.


• Graphs that admit right angle crossing drawings,
  • Karin Arikushi, Radoslav Fulek, Balázs Keszegh, Filip Morić;, and Csaba D. Tóth,
  • preliminary results in Abstracts of the 19th Fall Workshop on Comput. Geom. (Medford, MA, 2009), pp. 41-42,
    "Drawing graphs with 90° crossings and at most 1 or 2 bends per edge."
  • in Proc. 36th Workshop on Graph Theoretic Concepts in Comp. Sci. (Zarós, 2010), LNCS 6410, Springer, pp. 135-146.
  • Comput. Geom. Theory Appl. 45 (4) (2012), 169-177.
  • (abstract) We consider right angle crossing (RAC) drawings of graphs in which the edges are represented by polygonal arcs and any two edges can cross only at a right angle. We show that if a graph with n vertices admits an RAC drawing with at most 1 bend or 2 bends per edge, then the number of edges is at most 6.5n and 74.2n, respectively.


• Long non-crossing configurations in the plane,
  • Adrian Dumitrescu and Csaba D. Tóth,
  • in Proc. 27th Sympos. Theoretical Aspects of Comp. Sci. (Nancy, 2010), Leibniz International Proceedings in Informatics, Schloss Dagstuhl, pp. 311-322.
  • Discrete Comput. Geom. 44 (4) (2010), 727-752.
  • (abstract) We revisit some maximization problems for geometric networks design under the non-crossing constraint, first studied by Alon, Rajagopalan and Suri in the early 1990s. Given a set of n points in the plane in general position (no three points collinear), compute a longest non-crossing configuration composed of straight line segments that is: (a) a matching; (b) a Hamiltonian path; (c) a spanning tree. Here we obtain some new results for (b) and (c), as well as for the Hamiltonian cycle problem.


• New bounds on the average distance from the Fermat-Weber center of a planar convex body,
  • Adrian Dumitrescu, Minghui Jiang, and Csaba D. Tóth,
  • preliminary versions in Abstracts of the 18th Fall Workshop on Comput. Geom. (Troy, NY, 2008), pp. 61-62.
  • and in Proc. 20th Internat. Sympos. on Algorithms and Computation (Honolulu, HI, 2009), LNCS 5878, Springer, pp. 132-141.
  • Discrete Optimization 8 (3) (2011), 417-427.
  • (abstract) The Fermat-Weber center of a planar body Q is a point in the plane from which the average distance to the points in Q is minimal. We show that for any convex body Q in the plane, the average distance from the Fermat-Weber center of Q to the points of Q is larger than Δ(Q)/6, where Δ(Q) is the diameter of Q. This proves a conjecture of Paz Carmi, Sariel Har-Peled and Matthew Katz.


• A tight lower bound for convexly independent subsets of the Minkowski sums of planar point sets,
  • Ondřej Bílka, Kevin Buchin, Radoslav Fulek, Masashi Kiyomi, Yoshio Okamoto, Shin-ichi Tanigawa, and Csaba D. Tóth,
  • in Proc. 7th Japan Conference on Computational Geometry and Graphs (Kanazawa, 2009), JAIST.
  • Electronic Journal of Combinatorics 17 (1) (2010), article N35.
  • (abstract) For every m and n, there exist point sets P and Q in the plane with |P| = m and |Q| = n such that the Minkowski sum P+Q contains a convexly independent subset of size Ω(m^2/3n^2/3 + m + n). This bound is best possible by a recent result due to Eisenbrand, Pach, and Rothvoß.


• Augmenting the edge connectivity of planar straight line graphs to three,
  • Marwan Al-Jubeh, Mashhood Ishaque, Kristóf Rédei, Diane L. Souvaine, Csaba D. Tóth, and Pavel Valtr,
  • preliminary results (with Pavel Valtr) in Proc. XIII Encuentros de Geometría Computacional (Zaragoza, 2009).
  • preliminary results (with Marwan Al-Jubeh, Mashhood Ishaque, Kristóf Rédei, Diane L. Souvaine) "Tri-edge-connectivity augmentation for planar straight line graphs," in Proc. 20th Internat. Sympos. on Algorithms and Computation (Honolulu, HI, 2009), LNCS 5878, Springer, pp. 902-911.
  • Algorithmica 61 (4) (2011), 971-999.
  • (abstract) We characterize the planar straight line graphs (PSLGs) that can be augmented to 3-connected and 3-edge-connected PSLGs, respectively. We show that if a PSLG with n vertices can be augmented to a 3-edge-connected PSLG, then at most 2n-2 new edges are always sufficient and sometimes necessary for the augmentation. If the input PSLG is, in addition, already 2-edge-connected, then n-2 new edges are always sufficient and sometimes necessary for the augmentation to a 3-edge-connected PSLG.


• 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 5609, Springer, pp. 192-204.
  • J. Combinatorial Optimization 22 (3) (2010), 409-425.
  • (abstract) (pdf) 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.


• Binary plane partitions for disjoint line segments,
  • Csaba D. Tóth,
  • in Proc. 25th Sympos. on Comput. Geom. (Aarhus, 2009), ACM Press, pp. 71-79.
  • Discrete Comput. Geom. 45 (4) (2011), 617-646.
  • (abstract) (pdf) 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.


• Shooting permanent rays among disjoint polygons in the plane,
  • Mashhood Ishaque, Bettina Speckmann, and Csaba D. Tóth,
  • in Proc. 25th Sympos. on Comput. Geom. (Aarhus, 2009), ACM Press, pp 51-60.
  • SIAM J. Comput. 41 (4) (2012), 1005-1027.
  • (abstract) (pdf) 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. 42 (6-7) (2009), 522-535.
  • (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.


• On stars and Steiner stars II,
  • Adrian Dumitrescu, Csaba D. Tóth, and Guangwu Xu,
  • in 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)


• 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.


• Intersection patterns of curves,
  • Jacob Fox, János Pach, and Csaba D. Tóth,
  • J. London Math. Soc. 83 (2) (2011), 389-406.
    
  • (abstract) We prove that there are constants c >0 and c_k >0 for every k such that if a set C of n >1 curves in the plane, any two of which intersects in at most k points, contains at most ε n² intersecting pairs of curves, then there are two disjoint subsets A,B⊂ C, each of size at least c_kε^c n, with the property that every curve in A intersects every curve in B. It follows that for every k, there is a constant c'_k >0 such that for every collection C of n > 1 curves in the plane with no pair intersecting in more than k points, the intersection graph G of C or its complement G contains a balanced complete bipartite graph K_t,t with t≥ c'_k n; in other words, the family of intersection graphs of k-intersecting curves in the plane satisfies the strong Erdős-Hajnal property.


• Relative convex hulls in semi-dynamic arrangements,
  • Mashhood Ishaque and Csaba D. Tóth,
  • in Proc. 16th European Symposium on Algorithms (Karlsruhe, 2008), LNCS 5193, Springer, pp. 780-792.
  • Algorithmica 68 (2) (2014), 448-482.
  • (abstract) We present a data structure for maintaining the relative convex hull of a set of point sites in the presence of pairwise non-crossing line segment barriers that subdivide a bounding box into simply connected faces. For n sites and m barriers, our data structures have O((n+m) log n) size. They support m barrier insertions and O(n) site deletions in O((n+m)polylog (mn)) total time, and can answer analogues of standard convex hull queries in O(polylog(mn)) time.
    The semi-dynamic maintenance of the relative convex hull (with barrier insertions and site deletions) is motivated by a generalization of the sweep line technique, one of the most powerful methods in computational geometry. A sweep line scans a set of sites in a left-to-right order, which can be computed by sorting the sites by x-coordinate. Our data structures allow the sweep wavefront to have arbitrary polygonal shape, which is used in applications where the sweep wavefront has to bend around obstacles or stay in a configuration space. With previously known techniques, the m updates of a polygonal sweep wavefront required m simplex range reporting queries, hence O(m n^1/2 polylog n) total time. Our data structure reduces the runtime to O((m+n)polylog(mn)).


• 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.


• Connectivity augmentation in planar straight line graphs,
  • Csaba D. Tóth,
  • in Proc. Conf. on Topological & Geometric Graph Theory (Paris, 2008), pp. 51-54.
  • European J. Combinatorics 33 (3) (2012), 408-425.
  • (abstract) It is shown that every connected plane straight line graph with n≥ 3 vertices can be augmented to a 2-edge connected plane straight line graph by adding at most ⌊(2n-2)/3⌋ edges. It is also shown that every connected plane straight line tree with n≥ 3 vertices can be augmented to a 2-edge connected plane topological graph by adding at most ⌊n/2⌋ edges. Both bounds are best possible. However, for every n≥ 3, there are plane straight line trees with n vertices that cannot be augmented to a 2-edge-connected plane straight line graph by adding fewer than (6/11)n-O(1) edges, improving the previously known best lower bound of ⌊n/2⌋.


• Extremal problems on triangle areas in the plane and three-space,
  • Adrian Dumitrescu, Micha Sharir, and Csaba D. Tóth,
  • in Proc. 24th 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.


• 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.
    
  • Algorithmica 60 (3) (2011), 627-652.


• 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.
    


• Turán-type results for partial orders and intersection graphs of convex sets,
  • Jacob Fox, János Pach, and Csaba D. Tóth,
  • Israel J. of Math. 178 (2010), 29-50.
  • (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.


• 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.
    


• Disjoint segments have a convex partition with a 2-edge connected dual graph, (Erratum)
  • 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,
  • Jacob Fox, János Pach, and Csaba D. Tóth,
  • in Proc. 15th Sympos. on Graph Drawing (Sydney, 2007), LNCS 4875, Springer, 2008, pp. 13-24.
    
  • J. Combin. Theory, Ser. B 100 (1) (2010), 23-35.
  • (abstract) (pdf) The celebrated Crossing Lemma states that, in every drawing of a graph with n vertices and m ≥ 4n edges there are at least Ω(m³/n²) crossing edges; or equivalently, there is an edge that crosses Ω(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 Ω(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.


• Cuttings for disks and axis-aligned rectangles in three-space,
  • Eynat Rafalin, Diane L. Souvaine, and Csaba D. Tóth,
  • in Proc. 10th Workshop on Algorithms and Data Structures (Halifax, NS, 2007), LNCS 4619, Springer, pp. 470-482.
  • Discrete Comput. Geom. 43 (2) (2010), pp. 221-241.
  • (abstract) (pdf) 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.


• Improved throughput bounds for interference-aware wireless networks,
  • Chiranjeeb Buragohain, Subhash Suri, Csaba D. Tóth, and Yunhong Zhou,
  • in Proc. 13th Computing and Combinatorics Conference (Banff, AB, 2007), LNCS 4598, Springer, pp. 210-221.
  • (abstract) (1) Suppose we have n arbitrarily paired s-t pairs in an Θ(√ n) × Θ(√ n) size grid network. We show that if the average (hop) distance among the s-t pairs is d, then it is always possible to achieve a total throughput of Ω(n/d). There are instances where this bound is tight. The upper bound on the throughput follows easily from a packing argument; our contribution is to show that Ω(n/d) throughput is always achievable.
    (2) The Ω(n/d) throughput in a grid network can be achieved by a simple routing scheme that routes each flow along a single path. Both the routing and the scheduling algorithms are simple, deterministic, and distributed. Thus, for the grid topology networks, one can achieve (asymptotic) worst-case optimal throughput without resorting to computationally expensive LP type methods.
    (3) Our third result concerns an approximation bound for the throughput in a general network: arbitrary network topology and arbitrary s-t pairs. We capture the interference constraints at the node level, and impose an ordering on the nodes. As a result of these two ideas, we achieve an approximation ratio of 3 for the optimal throughput, improving all previous bounds.
    (4) We show that three straightforward routing schemes can have arbitrarily small throughput. On the other hand, in the special case of grid networks, we show that one can efficiently compute a single path route whose end to end throughput is within a constant factor of the optimal single path throughput. (erratum) There is a fatal error in our 3rd result. The solution of our LP-node linear program is not always schedulabable, as pointed out by Himanshu Gupta from SUNY Stone Brook. While LP-edge is still correct, it only gives a factor-5 approximation, instead of factor-3 claimed in the paper using LP-node.


• Distinct triangle areas in a planar point set,
  • Adrian Dumitrescu and Csaba D. Tóth,
  • in Proc. 12th Conf. on Integer Programming and Optimization (Ithaca, NY, 2007), LNCS 4513, 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.


• Light orthogonal networks with constant geometric dilation,
  • Adrian Dumitrescu and Csaba D. Tóth,
  • in Proc. 24th Sympos. Theoretical Aspects of Comp. Sci. (Aachen, 2007), LNCS 4393, Springer, pp. 175-187.
  • J. Discrete Algorithms 7 (1) (2009), 112-129.
  • (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 at vertices or in edges of the network, the shortest path between u and v is at most constant times longer than the (Euclidean) distance between u and v. (pdf)


• On the number of tetrahedra with minimal, unit, and distinct volumes in three-space,
  • Adrian Dumitrescu and Csaba D. Tóth,
  • in 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.


• On the decay of crossing numbers,
  • Jacob Fox and Csaba D. Tóth,
  • in Proc. 14th Sympos. on Graph Drawing (Karlsruhe, 2006), LNCS 4372, Springer, pp. 174-183.
  • J. Combin. Theory Ser. B 98 (1) (2008), 33-42.
  • (abstract) 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.


• Decompositions, partitions, and coverings with convex polygons and pseudo-triangles,
  
  • Oswin Aichholzer, Clemens Huemer, Sarah Kappes, Bettina Speckmann, and Csaba D. Tóth,
  • in Proc. 31st Sympos. Math. Foundations Comp. Sci. (Stará Lesná, 2006), LNCS 4162, 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)


• Spanning trees across axis-parallel segments,
  • Michael Hoffmann and Csaba D. Tóth,
  • in Proc. 18th Canadian Conf. Comput. Geom. (Kingston, ON, 2006), pp. 101-104.
  • (abstract) 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.


• Tight bounds for connecting sites across barriers,
  • David Krumme, Eynat Rafalin, Diane L. Souvaine, and Csaba D. Tóth,
  • in Proc. 22nd Sympos. Comput. Geom. (Sedona, AZ, 2006), ACM Press, pp. 439-448.
  • Discrete Comput. Geom. 40 (3) (2008), 377-394.
  • (abstract) 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.


• Distinct distances in homogeneous sets in Euclidean space,
  • József Solymosi and Csaba D. Tóth,
  • Discrete Comput. Geom. 35 (4) (2006), 537-549.
  • (abstract) 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 Ω(n^2/d-2/d(d+2)) for d≥4 (Solymosi and Vu, 2005) and Ω(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.


• A vertex-face assignment for plane graphs,
  • Diane L. Souvaine and Csaba D. Tóth,
  • in Proc. 17th Canadian Conf. on Comput. Geom. (Windsor, ON, 2005), pp. 131-134.
  • Comput. Geom. Theory Appl. 42 (5) (2009), 388-394.
  • (abstract) 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.


• Axis-aligned subdivisions with low stabbing numbers,
  • Csaba D. Tóth,
  • in Proc. 9th Workshop on Algorithms and Data Structures (Waterloo, ON, 2005), LNCS 3608, Springer, pp. 256-268.
  • SIAM J. Discrete Math. 22 (3) (2008), 1187-1204.
  • (abstract) 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.


• Space complexity of hierarchical heavy hitters in multi-dimensional data streams,
  • John Hershberger, Nisheeth Shrivastava, Subhash Suri, and Csaba D. Tóth,
  • in 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.


• Incidences of not-too-degenerate hyperplanes,
  • György Elekes and Csaba D. Tóth,
  • in Proc. 21st Sympos. Comput. Geom. (Pisa, 2005), ACM Press, pp. 16-21.
  • (abstract) 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. (pdf)


• Pointed and colored binary encompassing trees,
  • Michael Hoffmann and Csaba D. Tóth,
  • in Proc. 21st Sympos. Comput. Geom. (Pisa, 2005), ACM Press, pp. 81-90.
  • (abstract) 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.


• 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. 43 (1) (2010), 35-41.


• Detecting cuts in sensor networks,
  • Nisheeth Shrivastava, Subhash Suri, and Csaba D. Tóth,
  • in Proc. 4th International Conference on Information Processing in Sensor Networks (Los Angeles, CA, 2005), IEEE, pp. 210-217.
  • ACM Transactions on Sensor Networks 4 (2) (2008), article 10.
  • (abstract) 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/ε).


• Binary space partitions: recent developments,
  • Csaba D. Tóth,
  • in Combinatorial and Computational Geometry, vol. 52 of MSRI Publications, Cambridge University Press, 2005, pp. 529-556.


• Adaptive spatial partitioning for multidimensional data streams,
  • John Hershberger, Nisheeth Shrivastava, Subhash Suri, and Csaba D. Tóth,
  • in Proc. 15th International Symposium on Algorithms and Computation (Hong Kong, 2004), LNCS 3341, Springer, pp. 522-533.
  • Algorithmica 46 (2006), 97-117.


• Congestion games, load balancing, and price of anarchy,
  • Anshul Kothari, Subhash Suri, Csaba D. Tóth, and Yunhong Zhou,
  • in Proc. Workshop on Combinatorial and Algorithmic Aspects of Networking (Banff, AB, 2004), LNCS 3405, Springer, 2005, pp. 13-27.


• Encompassing colored crossing-free geometric graphs,
  • Ferran Hurtado, Mikio Kano, David Rappaport, and Csaba D. Tóth,
  • in 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.
  • in Proc. 9th Scandinavian Workshop on Algorithm Theory (Humlebæk, 2004), LNCS 3111, Springer, pp. 442-454.


• Selfish load balancing and atomic congestion games,
  • Subhash Suri, Csaba D. Tóth, and Yunhong Zhou,
  • in Proc. 16th ACM Sympos. on Parallelism in Algorithms and Architectures (Barcelona, 2004), ACM Press, 2004, pp. 188-195.
  • Algorithmica 47 (1) (2007), 79-96.
    
  • (pdf)


• Range counting over multidimensional data streams,
  • Subhash Suri, Csaba D. Tóth, and Yunhong Zhou,
  • in Proc. 20th Sympos. Comput. Geom. (Brooklyn, NY, 2004), ACM Press, pp. 160-169.
  • Discrete Comput. Geom. 36 (2006), 633-655.
    


• Binary space partition of orthogonal subdivisions,
  • John Hershberger, Subhash Suri, and Csaba D. Tóth,
  • in Proc. 20th Sympos. Comput. Geom. (Brooklyn, NY, 2004), ACM Press, pp. 230-238.
  • SIAM J. Comput. 34 (6) (2005), 1380-1397.


• Uncoordinated load balancing and congestion games in P2P systems,
  
  • Subhash Suri, Csaba D. Tóth, and Yunhong Zhou,
  • in Proc. 3rd Internat. Workshop on Peer-to-Peer Systems (La Jolla, CA, 2004), LNCS 3279, Springer, pp. 123-130.


• Degree bounds for constrained pseudo-triangulations,
  • Oswin Aichholzer, Michael Hoffmann, Bettina Speckmann, and Csaba D. Tóth,
  • in Proc. 15th Canadian Conf. Comput. Geom. (Halifax, NS, 2003), pp. 155-158.


• Binary space partition for axis-aligned fat rectangles,
  • Csaba D. Tóth,
  • in Proc. 11th European Symposium on Algorithms (Budapest, 2003), LNCS 2832, Springer, pp. 494-505.
  • SIAM J. Comput. 38 (1) (2008), 429-447.


• Alternating paths along axis-parallel segments,
  • Csaba D. Tóth,
  • Abstracts of 19th European Wrokshop on Comput. Geom. (Bonn, 2003), pp. 133-136.
  • in Proc. 8th Workshop on Algorithms and Data Structures (Ottawa, ON, 2003), LNCS 2748, Springer, 2003, pp. 389-400.
  • Graphs and Combinatorics 22 (2006), 527-543.
  • (pdf)


• Allocating vertex π-guards in simple polygons via pseudo-triangulations,
  • Bettina Speckmann and Csaba D. Tóth,
  • in 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.


• 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.


• Planar subdivisions,
  • Csaba D. Tóth,
  • PhD thesis, DISS ETH No. 14628, ETH Zürich, 2002.


• Binary space partition for line segments with a limited number of directions,
  • Csaba D. Tóth,
  • in 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.


• The k most frequent distances in the palne,
  • József Solymosi, Gábor Tardos, and Csaba D. Tóth,
  • Discrete Comput. Geom. 28 (4) (2002), 639-648.


• 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,
  • in Proc. 13th Canadian Conference on Comput. Geom. (Waterloo, ON, 2001), 109-112.
  • Comput. Geom. Theory Appl. 26 (1) (2003), 47-68.


• A note on binary plane partitions,
  • Csaba D. Tóth,
  • in Proc. 17th Sympos. on Comput. Geom. (Medford, MA, 2001), ACM Press, 2001, 151-156.
  • Discrete Comput. Geom. 30 (1) (2003), 3-16.


• Distinct distances in the plane,
  • József Solymosi and Csaba D. Tóth,
  • in Proc. 17th Sympos. on Comput. Geom. (Medford, MA, 2001), ACM Press, 2001, 29-31.
  • Discrete Comput. Geom. 25 (4) (2001), 629-634.


• Illuminating polygons with vertex π-floodlights,
  • Csaba D. Tóth,
  • in Proc. Int. Conf. on Comput. Sci. (San Francisco, CA, 2001) Part I, LNCS 2073, Springer, 2001, 772-781.


• Fault tolerant on-board networks with priorities,
  • Jean-Claude Bermond, Frédéric Havet, and Csaba D. Tóth,
  • in Proc. 3rd AlgoTel (Saint-Jean-de-Luz, 2001), pp. 95-98.
  • Networks 47 (1) (2006), 9-25.


• Guarding disjoint triangles and claws in the plane,
  • Csaba D. Tóth,
  • in 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.), LNCS 2098, Springer, 2001, 370-380.


• Illuminating labyrinths,
  • Csaba D. Tóth,
  • in 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 with 45º-floodlights,
  • Csaba D. Tóth,
  • Presented at the 4th Geometry Festival (Budapest, 1999).
  • Discrete Maths. 265 (1-3) (2003), 251-260.


• All-to-all routing and coloring in weighted trees of rings,
  • Bruno Beauquier, Stéphane Pérennes, and David Tóth,
  • in Proc. 11th ACM Sympos. on Parallel Algorithms and Architectures (Saint-Malo, 1999), ACM Press, 1999, 185-190.

Manuscripts