Search

Your search keyword '"Pach, J"' showing total 498 results
Start Over Author "Pach, J"
498 results on '"Pach, J"'

102. Uniformly distributed distances: A geometric application of Jansen's inequality

Author

Pach, J��nos and Spencer, Joel

Subjects
Mathematics::Commutative Algebra, FOS: Mathematics, Metric Geometry (math.MG), Physics::Atomic Physics
Abstract

Let $d_1\leq d_2\leq\ldots\leq d_{n\choose 2}$ denote the distances determined by $n$ points in the plane. It is shown that $\min\sum_i (d_{i+1}-d_i)^2=O(n^{-6/7})$, where the minimum is taken over all point sets with minimal distance $d_1 \geq 1$. This bound is asymptotically tight.

Published
1996
Full Text
View/download PDF

103. A Tverberg-type result on multicolored simplices

Author

Pach, J��nos

Subjects
Mathematics::Commutative Algebra, FOS: Mathematics, Mathematics::Mathematical Physics, Combinatorics (math.CO), Computer Science::Computational Geometry
Abstract

Let $P_1, P_2,\ldots, P_{d+1}$ be pairwise disjoint $n$-element point sets in general position in $d$-space. It is shown that there exist a point $O$ and suitable subsets $Q_i\subseteq P_i \; (i=1, 2, \ldots, d+1)$ such that $|Q_i|\geq c_d|P_i|$, and every $d$-dimensional simplex with exactly one vertex in each $Q_i$ contains $O$ in its interior. Here $c_d$ is a positive constant depending only on $d$.

Published
1996
Full Text
View/download PDF

110. Modeling Chronic Glycemic Exposure Variables as Correlates and Predictors of Microvascular Complications of Diabetes: Response to Orchard et al.

Author

Dyck, P. J., primary, Davies, J. L., additional, Clark, V. M., additional, Litchy, W. J., additional, Dyck, P. J. B., additional, Klein, C. J., additional, Rizza, R. A., additional, Pach, J. M., additional, Klein, R., additional, Larson, T. S., additional, Melton, L. J., additional, and O'Brien, P. C., additional

Published
2007
Full Text
View/download PDF

143. Common Tangents to Four Unit Balls in R 3.

Author

Macdonald, I. G., Pach, J., and Theobald, T.

Abstract

We answer a question of David Larman, by proving the following result. Any four unit balls in three-dimensional space, whose centers are not collinear, have at most twelve common tangent lines. This bound is tight. [ABSTRACT FROM AUTHOR]

Published
2001
Full Text
View/download PDF

146. How to draw a planar graph on a grid.

Author

Fraysseix, H., Pach, J., and Pollack, R.

Abstract

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 O(n) space, O( 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− o(1))√ n which settles a problem of Mohar. [ABSTRACT FROM AUTHOR]

Published
1990
Full Text
View/download PDF

147. A left-first search algorithm for planar graphs.

Author

Fraysseix, H., Mendez, P., and Pach, J.

Abstract

We give an O(| V( G)|)-time algorithm to assign vertical and horizontal segments to the vertices of any bipartite plane graph G so that (i) no two segments have an interior point in common, and (ii) two segments touch each other if and only if the corresponding vertices are adjacent. As a corollary, we obtain a strengthening of the following theorem of Ringel and Petrovič. The edges of any maximal bipartite plane graph G with outer face bwb′w′ can be colored by two colors such that the color classes form spanning trees of G−b and G−b′, respectively. Furthermore, such a coloring can be found in linear time. Our method is based on a new linear-time algorithm for constructing bipolar orientations of 2-connected plane graphs. [ABSTRACT FROM AUTHOR]

Published
1994
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results