Arrow Research search

Author name cluster

János Pach

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

17 papers
2 author rows

Possible papers

17

SODA Conference 2016 Conference Paper

Beyond the Richter-Thomassen Conjecture

  • János Pach
  • Natan Rubin
  • Gábor Tardos

If two closed Jordan curves in the plane have precisely one point in common, then it is called a touching point. All other intersection points are called crossing points. The main result of this paper is a Crossing Lemma for closed curves: In any family of n pairwise intersecting simple closed curves in the plane, no three of which pass through the same point, the number of crossing points exceeds the number of touching points by a factor of Ω((log log n ) 1/8 ). As a corollary, we prove the following long-standing conjecture of Richter and Thomassen: The total number of intersection points between any n pairwise intersecting simple closed curves in the plane, no three of which pass through the same point, is at least (1 – o (1)) n 2.

Details

FOCS Conference 2010 Conference Paper

On the Queue Number of Planar Graphs

  • Giuseppe Di Battista
  • Fabrizio Frati
  • János Pach

We prove that planar graphs have poly-logarithmic queue number, thus improving upon the previous polynomial upper bound. Consequently, planar graphs admit 3D straight-line crossing-free grid drawings in small volume.

Details

STOC Conference 2003 Conference Paper

Distinct distances in three and higher dimensions

  • Boris Aronov
  • János Pach
  • Micha Sharir
  • Gábor Tardos

Improving an old result of Clarkson et al., we show that the number of distinct distances determined by a set P of n points in three-dimensional space is Ω(n 77/141-ε )=Ω(n 0.546 ) , for any ε>0 . Moreover, there always exists a point p ∈ P from which there are at least these many distinct distances to the remaining elements of P . The same result holds for points on the three-dimensional sphere. As a consequence, we obtain analogous results in higher dimensions.

Details

FOCS Conference 2000 Conference Paper

On the boundary complexity of the union of fat triangles

  • János Pach
  • Gábor Tardos

A triangle is said to be /spl delta/-fat if its smallest angle is at least /spl delta/>0. A connected component of the complement of the union of a family of triangles is called hole. It is shown that any family of /spl delta/-far triangles in the plane determines at most O (n//spl delta/ log 2//spl delta/) holes. This improves on some earlier bounds of (Efrat et al. , 1993; Matousek et al. , 1994). Solving a problem of (Agarwal and Bern, 1999) we also give a general upper bound for the number of holes determined by n triangles in the plane with given angles. As a corollary, we obtain improved upper bounds for the boundary complexity of the union of fat polygons in the plane, which, in turn, leads to better upper bounds for the running times of some known algorithms for motion planning, for finding a separator line for a set of segments, etc.

Details

FOCS Conference 1998 Conference Paper

Which Crossing Number is it, Anyway?

  • János Pach
  • Géza Tóth 0001

A drawing of a graph G is a mapping which assigns to each vertex a point of the plane and to each edge a simple continuous arc connecting the corresponding two points. The crossing number of G is the minimum number of crossing points in any drawing of G. We define two new parameters, as follows. The pairwise crossing number (resp. the odd-crossing number) of G is the minimum number of pairs of edges that cross (resp. cross an odd number of times) over all drawings of G. We prove that the determination of each of these parameters is an NP-complete problem. We also prove that the largest of these numbers (the crossing number) cannot exceed twice the square of the smallest (the odd-crossing number). Our proof is based on the following generalization of an old result of Hanani, which is of independent interest. Let G be a graph and let E/sub 0/ be a subset of its edges such that there is a drawing of G, in which every edge belonging E/sub 0/ crosses any other edge an even number of times. Then G can be redrawn so that the element of E/sub 0/ are not involved in any crossing.

Details

TCS Journal 1992 Journal Article

Arrangements of curves in the plane—topology, combinatorics, and algorithms

  • Herbert Edelsbrunner
  • Leonidas Guibas
  • János Pach
  • Richard Pollack
  • Raimund Seidel
  • Micha Sharir

Arrangements of curves in the plane are fundamental to many problems in computational and combinatorial geometry (e. g. motion planning, algebraic cell decomposition, etc.). In this paper we study various topological and combinatorial properties of such arrangements under some mild assumptions on the shape of the curves, and develop basic tools for the construction, manipulation, and analysis of these arrangements. Our main results include a generalization of the zone theorem of Edelsbrunner (1986) and Chazelle (1985) to arrangements of curves (in which we show that the combinatorial complexity of the zone of a curve is nearly linear in the number of curves) and an application of that theorem to obtain a nearly quadratic incremental algorithm for the construction of such arrangements.

Details DOI

FOCS Conference 1991 Conference Paper

Fat Triangles Determine Linearly Many Holes

  • Jirí Matousek 0001
  • Nathaly Miller
  • János Pach
  • Micha Sharir
  • Shmuel Sifrony
  • Emo Welzl

It is shown that for every fixed delta >0 the following holds: if F is a union of n triangles, all of whose angles are at least delta, then the complement of F has O(n) connected components, and the boundary of F consists of O(n log log n) segments. This latter complexity becomes linear if all triangles are of roughly the same size or if they are all infinite wedges. A randomized algorithm that computes F in expected time O(n2/sup alpha (n)/ log n) is given. Several applications of these results are presented. >

Details

FOCS Conference 1989 Conference Paper

An Upper Bound on the Number of Planar k-Sets

  • János Pach
  • William L. Steiger
  • Endre Szemerédi

Given a set S of n points, a subset X of size k is called a k-set if there is a hyperplane II that separates X from X/sup c/. It is proved that O(n square root k/log/sub */k) is an upper bound for the number of k-sets in the plane, thus improving the previous bound of P. Erdos et al. (A Survey of Combinatorial Theory, North-Holland, 1983, p. 139-49) by a factor of log/sub */k. The method can be extended to give the bound O(n square root k/(log k)/sup epsilon /). The proof only establishes the weaker result; it uses the geometry and combinatorics together in a stronger way than in the earlier work. >

Details

STOC Conference 1988 Conference Paper

Small Sets Supporting Fáry Embeddings of Planar Graphs

  • Hubert de Fraysseix
  • János Pach
  • Richard Pollack

Answering a question of Rosenstiehl and Tarjan, we show that every plane graph with n vertices has a Fáry embedding (i.e., straight-line embedding) on the 2 n - 4 by n - 2 grid and provide an Ο( n ) space, Ο( n log n ) time algorithm to effect this embedding. The grid size is asymptotically optimal and it had been previously unknown whether one can always find a polynomial sized grid to support such an embedding. On the other hand we show that any set F , which can support a Fáry embedding of every planar graph of size n , has cardinality at least n + (1 - ο (1)) √ n which settles a problem of Mohar.

Details

FOCS Conference 1987 Conference Paper

On the Lower Envelope of Bivariate Functions and its Applications

  • Herbert Edelsbrunner
  • János Pach
  • Jacob T. Schwartz
  • Micha Sharir

We consider the problem of obtaining sharp (nearly quadratic) bounds for the combinatorial complexity of the lower envelope (i. e. pointwise minimum) of a collection of n bivariate (or generally multi-variate) continuous and "simple" functions, and of designing efficient algorithms for the calculation of this envelope. This problem generalizes the well-studied univariate case (whose analysis is based on the theory of Davenport-Schinzel sequences), but appears to be much more difficult and still largely unsolved. It is a central problem that arises in many areas in computational and combinatorial geometry, and has numerous applications including generalized planar Voronoi diagrams, hidden surface elimination for intersecting surfaces, purely translational motion planning, finding common transversals of polyhedra, and more. In this abstract we provide several partial solutions and generalizations of this problem, and apply them to the problems mentioned above. The most significant of our results is that the lower envelope of n triangles in three dimensions has combinatorial complexity at most O(n2α(n)) (where α(n) is the extremely slowly growing inverse of Ackermann's function), that this bound is tight in the worst case, and that this envelope can be calculated in time O(n2α(n)).

Details
v2026.09.13