Csaba D. Tóth
Associate Professor
Department of Mathematics
California State University, Northridge
Room SN 434, 18111 Nordhoff St.
Northridge, CA 913308313
Phone: (818) 6772826
cdtoth ♠ acm.org
Publications
in reverse chronological order (see also DBLP)

Atomic embeddability, clustered planarity, and thickenability,

On the Cover of the Rolling Stone,

Simple kplanar 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, Twoplanar 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 (2019), to appear.
 (abstract)
A simple topological graph is kquasiplanar (k≥ 2) if it contains no k pairwise crossing edges, and kplanar if no edge is crossed more than k times. In this paper, we explore the relationship between kplanarity and kquasiplanarity to show that, for k≥2, every kplanar simple topological graph can be transformed into a (k+1)quasiplanar simple topological graph.

On the stretch factor of a polygonal chain,

Rock climber distance: Frogs versus dogs,

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

Perfect rainbow polygons for colored point sets in the plane,
 David FloresPeñaloza, Mikio Kano, Leonardo MartínezSandoval, 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. 4346.

Circumscribing polygons and polygonizations for disjoint line segments,

Convex polygons in Cartesian products,
 JeanLou 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.

Reconstruction of the crossing type of a point set from the compatible exchange graph of noncrossing spanning trees,

Online unit covering in Euclidean space,

Improved bounds on information dissemination by Manhattan random waypoint model,

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. 229241.
 (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^{2}. 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^{2} with φψ_{ε}<ε,
where . is the uniform norm (i.e., sup norm).
We present a polynomialtime 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 NPcomplete (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. 5460.
 (abstract)
Let P and Q be finite point sets of the same cardinality in R^{2}, 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 straightline embeddings of the same connected nvertex graph G. No polynomialtime 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 polynomialtime algorithms to find compatible paths or report that none exist in three scenarios:
O(n) time for points in convex position; O(n^{2}) time for two simple polygons, where the paths are restricted to remain inside the closed polygons; and O(n^{2} log n) time for points in general position if the paths are restricted to be monotone.

Maximum area axisaligned 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:177:15.
 (abstract)
Given a point set S={s_{1},...,s_{n}} in the unit square U=[0,1]^{2}, an anchored square packing is a set of n interiordisjoint 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 NPcomplete. 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. 835838.
 (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 straightline 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. ACMSIAM Symposium on Discrete Algorithms (New Orleans, LA, 2018), pp. 274292.
 ACM Transactions on Algorithms (2019), to appear.
 (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 interiordisjoint 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 polynomialtime 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_{2}, 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.

Gapplanar graphs,
 Sang Won Bae, JeanFrancois Baffier, Jinhee Chun, Peter Eades, Kord Eickmeyer, Luca Grilli, SeokHee 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, 531545.
 Theoretical Computer Science 745 (2018), 3652.
 (abstract)
We introduce the family of kgapplanar 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 kgapplanar graph can be drawn crossingfree 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 beyondplanar 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. 238252.
 (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^{2})
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. 198201.
 Computational Geometry: Theory and Applications (2018), to appear.
 (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 straightline 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. 204216.
 Theoretical Computer Science 789 (2019), 5063.
 (abstract)
We consider edge insertion and deletion operations that increase the connectivity of a given planar straightline 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 2connected 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^{4}) time; however the problem becomes NPhard 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 straightline 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) 161180.
 (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 NPcomplete 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 worstcase upper and lower bounds for both problems.

Multicolored 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. 8193.
 (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 MinCSG}problem asks for the minimum sum of edge length in a colored spanning graph.
We show that the problem is NPhard 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.

Constantfactor 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. 375390.
 (abstract)
We revisit the traveling salesman problem with neighborhoods (TSPN) and present the first constantratio 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 constantratio 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. 411422.
 Theory of Computing Systems 62 (6) (2018), 14901524.
 (abstract)
We prove that the (maximum) number of monotone paths in a triangulation of n points in the plane is O(1.8026^{n}). This improves an earlier upper bound of O(1.8393^{n}) established by Löffler et al. (2013). The current best lower bound of Ω(1.7034^{n}) is due to the same authors.
Given a planar straightline graph G with n vertices, we show that the number of monotone paths in G can be computed in O(n^{2}) time.
 A note on independent hyperplanes and general position subsets in dspace,

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 ngon is weakly simple. This improves upon an O(n^{2} 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), 131162.
 (abstract)
For points p_{1},...,p_{n} in the unit square [0,1]^{2},
an anchored rectangle packing consists of interiordisjoint
axisaligned empty rectangles r_{1},...,r_{n} ⊂ [0,1]^{2}
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]^{2}, there is an anchored rectangle packing
of area at least 7/12O(1/n), and for every n∈N, there are
nelement 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_{1} and T_{2} on n vertices and have to find a planar graph on n vertices that is the edgedisjoint union of T_{1} and
T_{1}. 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 nonstar trees.

Note on kplanar 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), 26.
 (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 kplanar crossing number of G,
cr_{k}(G), is defined as the minimum of cr(G_{0})+cr(G_{1})+...+cr(G_{k1}) over all graphs
G_{0}, G_{1},...,G_{k1} with G=G_{0}∪G_{1}∪...∪G_{k1}.
It is shown that for every k≥1, we have cr_{k}(G)≤ ((2/k^{2})(1/k^{3}))cr(G).
This bound does not remain true if we replace the constant ((2/k^{2})(1/k^{3})) by any number
smaller than 2/k^{2}. Some of the results extend to the rectilinear variants of the kplanar crossing number.
 Linearsize universal point sets for onebend 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. 423429.
 (abstract)
For every integer n≥ 4, we construct a planar point set S_{n} of size 6n10
such that every nvertex 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. 447459.
 (abstract)
We wish to decide whether a simply connected flexible polygonal structure can be realized in Euclidean space. Two models are considered: polygonal linkages (bodyandjoint framework) and contact graphs of unit disks in the plane. (1) We show that it is strongly NPhard 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 NPhard already for a chain of rectangles. (2) We also show that it is strongly NPhard to decide whether a given tree is the contact graph of interiordisjoint 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. 377389.
 Theoretical Computer Science 654 (2016), 143–154.
 (abstract)
We consider packing axisaligned rectangles r_{1},... , r_{n} in the unit square [0,1]^{2} 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 lowerleft corners of the rectangles, then the number of maximal packings is shown to be at most 2^{n}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. 289300.
 Combinatorics, Probability, and Computing 26 (5) (2017), 641659.
 (abstract)
We show that the maximum number of convex polygons in a triangulation of n points in the
plane is O(1.5029^{n}). This improves an earlier bound of O(1.6181^{n}) established by van Kreveld, Löffler, and Pach (2012) and almost matches the current best lower bound of Ω(1.5028^{n}) due
to the same authors. Given a planar straightline 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 (MingYang 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. 197210.
 Computational Geometry: Theory and Applications 68 (2018), 206225.
 (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
4connectivity as a means to establish Hamiltonicity. But in general about
3n/5 flips are necessary to reach a 4connected triangulation. Our result
improves the upper bound on the diameter of the combinatorial flip graph of
triangulations on n vertices from 5.2n33.6 to 5n23. We also show that
for every triangulation on n vertices there is a simultaneous flip of less
than 2n/3 edges to a 4connected 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
3n6) edges the resulting graph admits a 2page book embedding.
 Disjoint edges in topological graphs and the tangledthrackle conjecture,
 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_{1},...,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_{2} 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^{3}_{n}
can be covered by an axisaligned polygonal path with (3/2)n^{2}+O(n)
edges, thus in particular by a polygonal tree with that many edges. Here we show that every covering
tree for the n^{3} points of G^{3}_{n}
has at least (1+c_{3})n^{2} edges, for some constant c_{3}>0.
On the other hand, there exists a covering tree for the n^{3} points of G^{3}_{n} consisting of only n^{2}+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}_{n}for
d ≥ 3) are also examined.
 The SzemerédiTrotter Theorem in the complex plane,
 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. 128143.
 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 exponentialtime algorithm that computes an
interiorrestricted barrier made of segments for any given convex
ngon. 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 FoxEpstein, Csaba D. Tóth, and Andrew Winslow
 in Proc. 20th Computing and Combinatorics Conference (Atlanta, GA, 2014), LNCS 8591, Springer, pp. 239250.
 Algorithmica 76 (4) (2016), 910931.
 (abstract)
It is shown that every simple polygon with n walls can be illuminated from a single point light source s after at most ⌊(n2)/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. 242250.
 SIAM J. Discrete Math. 31 (2) (2017), 11741195.
 (abstract)
It is shown that on every nelement 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 straightline 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 straightline edges: for example, the number of plane graphs realizable with xmonotone edges on n points is already superexponential.
 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. 426435.
 Discrete and Computational Geometry 54 (1) (2015), 259289.
 (abstract)
We study straightline 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 straightline 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_{k} provides a new version of the celebrated carpenter's rule problem. Even though cycles C_{k}, 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 4connected 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. 478489.
 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 112.
 J. Graph Algorithms and Applications 18 (2) (2014), 253279.
 (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 ydirection 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 lineartime testing algorithms for two classes of mixed plane triangulations, namely mixed plane 3trees 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. 96109.
 Contributions to Algebra and Geometry 56 (2) (2015), 515532.
 (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), 427452.
 (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 5connected biplane
graph and that there are arbitrarily large point sets that do not admit any 6connected
biplane graph. Furthermore, we show that every plane graph (other than the wheel or the
fan) can be augmented into a 4connected biplane graph. However, there are arbitrarily
large plane graphs that cannot be augmented to a 5connected 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), 407425.
 (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 nelement 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. 163168.
 Graphs and Combinatorics 32 (3) (May, 2016), 923942.
 (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 starshaped polygons and monotone paths.
We also consider related problems in directed planar
straightline graphs.
 A tight bound for point guards in piecewise convex art galleries,
 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 threetrees,
 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), 101112.
 (abstract)
For every positive integer n, we present a set S_{n} of O(n^{3/2}log n) points in the plane such that every planar 3tree with n vertices has a straightline 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 3trees, as well as for the class of 2trees and serial parallel graphs.
 Vertexcolored encompassing graphs,
 Diffuse reflections in simple polygons,
 Gill Barequet, Sarah M. Cannon, Eli FoxEpstein, Benjamin Hescott, Diane L. Souvaine, Csaba D. Tóth, and Andrew Winslow,
 in Proc. VII LatinAmerican Algorithms, Graphs and Optimization Symposium (Playa del Carmen, 2013), Electronic Notes in Discrete Mathematics 44 (5) (2013), 345–350.
 Discrete Applied Mathematics 210 (2016), 123132.
 (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 ACMSIAM Symposium on Discrete Algorithms
(New Orleans, LA, 2013), SIAM, pp. 828843.
 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 3space).
(I) Given a set of n planes in 3space, 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 3space, a TSP tour that is at most O(log^{3}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 3space), 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 JapaneseHungarian Symposium on Discrete Mathematics and Its Applications (Veszprém, 2013).
 Discrete Comput. Geom. 51 (2) (2014), 462484.
 (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 n1 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 selfcrossing) 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 nelement point sets that require at least 5n/9 O(1) segments in any such path. Further, we show that computing a noncrossing covering path for n points in the plane requires Ω(n log n) time in the worst case.
 Edge guards for polyhedra in threespace,
 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. 103114.
 J. Graph Algorithms and Applications 18 (3) (2014), 401420.
 (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 nvertex 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 straightline 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. 79104.
 (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,
 Conflictfree 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. 5768.
 (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 NPcomplete 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 ACMSIAM Sympos. on Discrete Algorithms (Kyoto, 2012), SIAM, 2012, pp. 294305.
 Combinatorica 35 (1) (2015), 3961.
 (abstract)
Let S be a set of n points in the unit square [0,1]^{2},
one of which is the origin. We construct n pairwise interiordisjoint axisaligned
empty rectangles such that the lowerleft 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. 327354.
 (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 crossingfree straightline 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 triconnected planar straight line graphs,
 Marwan AlJubeh, 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 vertexdisjoint 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. 4970.
 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. 290295.
 SIAM J. Discrete Math. 28 (4) (2014), 19351943.
 (abstract)
For every positive integer n, there is a straightline drawing D_{n}
of a planar graph on n vertices such that in any crossingfree straightline
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. 449454.
 in Computational Geometry (A. Marquez et al., eds.), LNCS 7579, Springer, 2012, pp. 5464.
 (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
nonstarshaped 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 ngon 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,
 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. 137140.
 in Computational Geometry (A. Marquez et al., eds.), LNCS 7579, Springer, 2012, pp. 138145.
 (abstract)
We show that every straightline 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. 524535.
 in Thirty Essays on Geometric Graph Theory (J. Pach, ed.), Springer, 2013, pp. 303326.
 (abstract)
We generalize the notions of flippable
and simultaneouslyflippable edges in a triangulation of a set S of points in the plane, into so called
pseudosimultaneously flippable edges. Such edges are related to the notion of convex decompositions spanned by S.
We derive a worstcase tight lower bound on the number of pseudosimultaneously 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 crossingfree 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, cyclefree graphs).
We also obtain upper bounds for the number of crossingfree
straightedge 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. 125134.
 Discrete Comput. Geom.49 (1) (2013), 89131.
 (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 edgedisjoint spanning trees.
 Bounds on the maximum multiplicity of some common geometric graphs,
 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. 324338.
 Comput. Geom. Theory Appl. 46 (2013), 574590.
 (abstract)
A simplex spanned by a colored point set in Euclidean dspace is
colorful if all vertices have distinct colors. The union of all
fulldimensional 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^{(d1)2}) and
O(n^{(d1)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^{4} α(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^{d1}) hyperplanes, and the colorful union
is the union of d+1 starshaped 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. 112.
 SIAM J. Discrete Math. 26 (1) (2012), 305320.
 (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. 113116.
 Comput. Geom. Theory Appl. 45 (7) (2012), 326333.
 (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 NPhard 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 3space. 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. 4142,
"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. 135146.
 Comput. Geom. Theory Appl. 45 (4) (2012), 169177.
 (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 noncrossing 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. 311322.
 Discrete Comput. Geom. 44 (4) (2010), 727752.
 (abstract)
We revisit some maximization problems for geometric networks design
under the noncrossing 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 noncrossing 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
FermatWeber 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. 6162.
 and in Proc. 20th Internat. Sympos. on Algorithms and Computation (Honolulu, HI, 2009),
LNCS 5878, Springer, pp. 132141.
 Discrete Optimization 8 (3) (2011), 417427.
 (abstract)
The FermatWeber 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
FermatWeber 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 HarPeled 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, Shinichi 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/3}n^{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 AlJubeh, 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 AlJubeh, Mashhood Ishaque, Kristóf Rédei, Diane L. Souvaine)
"Triedgeconnectivity augmentation for planar straight line graphs,"
in Proc. 20th Internat. Sympos. on Algorithms and Computation
(Honolulu, HI, 2009),
LNCS 5878, Springer, pp. 902911.
 Algorithmica 61 (4) (2011), 971999.
 (abstract)
We characterize the planar straight line graphs (PSLGs) that can be augmented
to 3connected and 3edgeconnected PSLGs, respectively. We show that
if a PSLG with n vertices can be augmented to a 3edgeconnected PSLG, then at
most 2n2 new edges are always sufficient and sometimes necessary for the augmentation.
If the input PSLG is, in addition, already 2edgeconnected, then n2
new edges are always sufficient and sometimes necessary for the augmentation to a
3edgeconnected PSLG.
 Convex partitions with 2edge connected dual graphs,
 Marwan AlJubeh, 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. 6364.
 in Proc. 15th Internat. Computing and Combin. Conf. (Niagara Falls, NY, 2009),
LNCS 5609, Springer, pp. 192204.
 J. Combinatorial Optimization
22 (3) (2010), 409425.

(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 nk+1 convex
cells whose dual graph is 2edge 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. 7179.
 Discrete Comput. Geom. 45 (4) (2011), 617646.
 (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 5160.
 SIAM J. Comput. 41 (4) (2012), 10051027.
 (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^{2} 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 nearlinear
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 halfline 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 semidynamic 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^{2} 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 (67) (2009), 522535.
 (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, 2n4 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 ACMSIAM Sympos. on Discrete Algorithms (New York, NY, 2009), ACM Press, pp. 311317.
 Discrete Optimization 6 (3) (2009), 324332.
 (abstract)
A Steiner star for a set P of n points in dspace connects an
arbitrary center point to all points of P, while a
star connects a point p∈ P to the remaining n1 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
dspace. The maximum ratio between them, over all finite point configurations
in dspace, is called the star Steiner ratio in dspace.
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 3space, 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), 217225.
 (abstract)
It is shown that for every subdivision of the ddimensional Euclidean space, d≥ 2, into n convex cells, there is a straight line that stabs at least Ω((log n,/loglog n)^{1/(d1)}) cells. This bound is best possible apart from a constant factor. In other words, if a convex subdivision of dspace has the property that any line stabs at most k convex cells, then the subdivision has at most exp(O(k^{{d1}}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), 389406.
 (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^{2}
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 kintersecting curves in the plane satisfies the strong ErdősHajnal property.
 Relative convex hulls in semidynamic arrangements,
 Mashhood Ishaque and Csaba D. Tóth,
 in Proc. 16th European Symposium on Algorithms
(Karlsruhe, 2008), LNCS 5193, Springer, pp. 780792.
 Algorithmica 68 (2) (2014), 448482.
 (abstract)
We present a data structure for maintaining the relative convex hull of a set of point sites in the presence
of pairwise noncrossing 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 semidynamic 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 lefttoright order, which can be computed by sorting
the sites by xcoordinate. 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), 617625.
 (abstract)
Given a set of s points and a set of n^{2}
lines in threedimensional 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. 5154.
 European J. Combinatorics 33 (3) (2012), 408425.
 (abstract)
It is shown that every connected plane straight line graph with
n≥ 3 vertices can be augmented to a 2edge connected plane straight line graph by adding at most ⌊(2n2)/3⌋
edges. It is also shown that every connected plane straight line tree with n≥ 3 vertices can be augmented to a 2edge 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 2edgeconnected plane straight
line graph by adding fewer than (6/11)nO(1) edges, improving the previously known best lower bound of ⌊n/2⌋.
 Extremal problems on triangle areas in the plane and
threespace,
 Adrian Dumitrescu, Micha Sharir, and Csaba D. Tóth,
 in Proc. 24th
Sympos. Comput. Geom. (College Park, MD, 2008), ACM Press, pp. 208217.
 J. Combin. Theory Ser. A 116 (2009), 11771198.
 (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 nelement 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^{2}n); there exist nelement
point sets that span (6/π^{2}o(1))n^{2} 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 nelement point sets that
span Ω(n log n) minimum area triangles.
In threespace 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^{2}); this is asymptotically
tight. (iv) There exist nelement point sets that span Ω(n^{4/3})
triangles of maximum area.
 Minimum weight convex Steiner partitions,
 On stars and Steiner stars,
 Turántype
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), 2950.
 (abstract)
We prove several Ramseytype 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 xmonotone 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 sweepline algorithms for constructing spanning trees and Steiner trees,
 Disjoint segments have a convex partition with a 2edge 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. 1316.
 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. 1324.
 J. Combin. Theory, Ser. B 100 (1) (2010), 2335.
 (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^{3}/n^{2}) crossing edges; or equivalently, there is
an edge that crosses Ω(m^{2}/n^{2}) 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_{1} , E_{2} ⊂ E, each of size
Ω(m^{2}/n^{2}), such that every edge in E_{1} crosses
every edge in E_{2}. 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 axisaligned rectangles in threespace,
 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. 470482.
 Discrete Comput. Geom. 43 (2) (2010), pp. 221241.

(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
divideandconquer 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^{2}) for every finite set of disjoint disks in
3space; and there is an (1/r)cutting of size
O(r^{3/2}) for every finite set of disjoint
axisaligned rectangles in 3space. Both bounds are best possible.
 Improved throughput bounds for interferenceaware 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. 210221.

(abstract)
(1) Suppose we have n arbitrarily paired st pairs in an Θ(√ n) × Θ(√ n) size grid network. We show that if the average (hop) distance among the st 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) worstcase 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 st 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 LPnode linear program is not always schedulabable, as pointed out by Himanshu Gupta from SUNY Stone Brook. While LPedge is still correct, it only gives a factor5 approximation, instead of factor3 claimed in the paper using LPnode.
 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. 119129.

(abstract)
Erdős, Purdy, and Straus (1977) conjectured that n
noncollinear points in the plane determine at least
⌊(n1)/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/38O(1)≈ 0.4473n. The best previous
bound, (√2 1)nO(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. 175187.
 J. Discrete Algorithms
7 (1) (2009), 112129.

(abstract)
An
orthogonal network for a given set of n points in the
plane is an axisaligned 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 threespace,
 Adrian Dumitrescu and Csaba D. Tóth,
 in Proc. 18th ACMSIAM Sympos. on Discrete Algorithms (New Orleans, LA, 2007), ACM Press, pp. 11141123.
 Combinatorics Probability and Computing 17 (2008), 203224.

(abstract)
We
formulate and give partial answers to several combinatorial
problems on fourtuples of n points in threespace. (i)
The number of minimum (nonzero) volume tetrahedra spanned by
n points in R^{3} is
Θ(n^{3}). (ii) The number of unitvolume
tetrahedra determined by n points in
R^{3} is O(n^{7/2}), and there
are point sets for which this number is
Ω(n^{3}log log n). (iii) The
tetrahedra determined by n points in
R^{3}, 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 threedimensional case to an old
question of Erdős, Purdy, and Straus. We also give an
O(n^{3}) 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. 174183.
 J. Combin. Theory Ser. B 98 (1) (2008), 3342.

(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 pseudotriangles,
 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. 8697.
 Graphs and Combinatorics 23 (5) (2007), 481507.

(abstract)
We propose a novel subdivision of the plane that consists of
both convex polygons and pseudo triangles. This pseudoconvex
decomposition is significantly sparser than either convex
decompositions or pseudotriangulations for planar point sets
and simple polygons. We also introduce pseudoconvex
partitions and coverings. We establish some basic properties
and give combinatorial bounds on their complexity. Our upper
bounds depend on new Ramseytype results concerning disjoint
empty convex kgons in point sets.
(pdf)
 Spanning
trees across axisparallel segments,
 Michael Hoffmann and Csaba D. Tóth,
 in Proc. 18th Canadian Conf. Comput. Geom. (Kingston, ON, 2006), pp. 101104.

(abstract)
Given n
disjoint axisparallel 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. 439448.
 Discrete Comput. Geom. 40 (3) (2008), 377394.

(abstract)
This result was motivated by a multipoint location problem, a central
question in computational geometry. Assume that we are given n
pairwise noncrossing 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 segmentedge 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), 537549.

(abstract)
The minimum number of distinct distances determined by n points
in dspace is between the upper bound O(n^{2/d}) (in
the integer lattice section); and the lower bounds
Ω(n^{2/d2/d(d+2)}) for d≥4 (Solymosi
and Vu, 2005) and Ω(n^{.5460}) in 3space (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
dspace and Ω(n^{.6091}) distinct distances in
3space.
 A vertexface assignment for
plane graphs,
 Diane L. Souvaine and Csaba D. Tóth,
 in Proc. 17th Canadian
Conf. on Comput. Geom. (Windsor, ON, 2005), pp. 131134.
 Comput. Geom. Theory Appl.
42 (5) (2009), 388394.

(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 vertexcolored
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 pseudotriangulations by (Haas et al., 2005),
extending Henneberg operations.
 Axisaligned
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. 256268.
 SIAM J. Discrete Math. 22 (3) (2008), 11871204.

(abstract)
An orthogonal subdivision in dspace is the partition of the
space into axisaligned boxes. It is shown that for any orthogonal
subdivision of size n, there is an axisparallel line that
intersects the interior of (that is, stabs) at least
Ω(log^{1/(d1)}n) boxes. Constructions are
also given for d≥2, where this bound is attained.
 Space
complexity of hierarchical heavy hitters in multidimensional 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. 338347.

(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 multidimensional 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 userspecified parameter and
n is the size of the data set. Recently, singlepass 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 singlepass deterministic scheme that
computes φHHHs in a ddimensional 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 nottoodegenerate
hyperplanes,
 György Elekes and Csaba D. Tóth,
 in Proc. 21st Sympos. Comput. Geom. (Pisa, 2005), ACM Press, pp. 1621.

(abstract)
We prove a new SzemerédiTrottertype bound on pointhyperplane
incidences in dspace. 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 nontrivial upper bound. In this paper we consider
saturated hyperplanes only. In 3space a plane containing
k points is saturated if these points span at least
Ω(k^{2}) 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^{d1}/k^{d1}).
This is equivalent with the SzemerédiTrotter 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. 8190.

(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 vertexcolored 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,
 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. 210217.
 ACM Transactions on Sensor Networks
4 (2) (2008), article 10.

(abstract)
This is a result about "twosided" ε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. 529556.
 Adaptive spatial partitioning for multidimensional data streams,
 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. 1327.
 Encompassing colored crossingfree geometric graphs,
 Pointed binary encompassing trees,
 Selfish load balancing and atomic
congestion games,
 Range counting over multidimensional
data streams,
 Binary space partition of orthogonal
subdivisions,
 Uncoordinated
load balancing and congestion games in P2P systems,
 Degree bounds for constrained pseudotriangulations,
 Binary space partition for axisaligned fat rectangles,
 Alternating paths along axisparallel segments,
 Csaba D. Tóth,
 Abstracts of 19th European Wrokshop on Comput. Geom. (Bonn, 2003), pp. 133136.
 in Proc. 8th Workshop on Algorithms and Data Structures (Ottawa, ON, 2003), LNCS 2748, Springer, 2003, pp. 389400.
 Graphs and Combinatorics 22 (2006), 527543.
 (pdf)
 Allocating vertex πguards in simple polygons via pseudotriangulations,
 Illuminating disjoint line segments in the plane,
 Alternating paths through disjoint line segments,
 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,
 The k most frequent distances in the palne,
 Illumination in the presence of opaque line segments in the plane,
 Art galleries with guards of uniform range of vision,
 Segment endpoint visibility graphs are Hamiltonian,
 A note on binary plane partitions,
 Distinct distances in the plane,
 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, 772781.
 Fault tolerant onboard networks with priorities,
 JeanClaude Bermond, Frédéric Havet, and Csaba D. Tóth,
 in Proc. 3rd AlgoTel (SaintJeandeLuz, 2001), pp. 9598.
 Networks 47 (1) (2006), 925.
 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 (12) (2003), 5165.

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, 370380.
 Illuminating labyrinths,
 Art gallery problem with guards whose range of vision is 180º,
 Illumination of polygons with 45ºfloodlights,
 Csaba D. Tóth,
 Presented at the 4th Geometry Festival (Budapest, 1999).
 Discrete Maths. 265 (13) (2003),
251260.
 Alltoall 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 (SaintMalo, 1999), ACM Press, 1999, 185190.
Manuscripts