Search Results

Documents authored by Raz, Orit E.

Document
DOI: 10.4230/LIPIcs.SoCG.2021.35
On Rich Lenses in Planar Arrangements of Circles and Related Problems

Authors: Esther Ezra, Orit E. Raz, Micha Sharir, and Joshua Zahl

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
We show that the maximum number of pairwise non-overlapping k-rich lenses (lenses formed by at least k circles) in an arrangement of n circles in the plane is O(n^{3/2}log(n / k^3) k^{-5/2} + n/k), and the sum of the degrees of the lenses of such a family (where the degree of a lens is the number of circles that form it) is O(n^{3/2}log(n/k^3) k^{-3/2} + n). Two independent proofs of these bounds are given, each interesting in its own right (so we believe). We then show that these bounds lead to the known bound of Agarwal et al. (JACM 2004) and Marcus and Tardos (JCTA 2006) on the number of point-circle incidences in the plane. Extensions to families of more general algebraic curves and some other related problems are also considered.
Cite as

Esther Ezra, Orit E. Raz, Micha Sharir, and Joshua Zahl. On Rich Lenses in Planar Arrangements of Circles and Related Problems. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 35:1-35:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ezra_et_al:LIPIcs.SoCG.2021.35,
  author =	{Ezra, Esther and Raz, Orit E. and Sharir, Micha and Zahl, Joshua},
  title =	{{On Rich Lenses in Planar Arrangements of Circles and Related Problems}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{35:1--35:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.35},
  URN =		{urn:nbn:de:0030-drops-138343},
  doi =		{10.4230/LIPIcs.SoCG.2021.35},
  annote =	{Keywords: Lenses, Circles, Polynomial partitioning, Incidences}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.65
Dense Graphs Have Rigid Parts

Authors: Orit E. Raz and József Solymosi

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
While the problem of determining whether an embedding of a graph G in ℝ² is infinitesimally rigid is well understood, specifying whether a given embedding of G is rigid or not is still a hard task that usually requires ad hoc arguments. In this paper, we show that every embedding (not necessarily generic) of a dense enough graph (concretely, a graph with at least C₀n^{3/2}(log n)^β edges, for some absolute constants C₀>0 and β), which satisfies some very mild general position requirements (no three vertices of G are embedded to a common line), must have a subframework of size at least three which is rigid. For the proof we use a connection, established in Raz [Discrete Comput. Geom., 2017], between the notion of graph rigidity and configurations of lines in ℝ³. This connection allows us to use properties of line configurations established in Guth and Katz [Annals Math., 2015]. In fact, our proof requires an extended version of Guth and Katz result; the extension we need is proved by János Kollár in an Appendix to our paper. We do not know whether our assumption on the number of edges being Ω(n^{3/2}log n) is tight, and we provide a construction that shows that requiring Ω(n log n) edges is necessary.
Cite as

Orit E. Raz and József Solymosi. Dense Graphs Have Rigid Parts. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 65:1-65:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{raz_et_al:LIPIcs.SoCG.2020.65,
  author =	{Raz, Orit E. and Solymosi, J\'{o}zsef},
  title =	{{Dense Graphs Have Rigid Parts}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{65:1--65:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.65},
  URN =		{urn:nbn:de:0030-drops-122236},
  doi =		{10.4230/LIPIcs.SoCG.2020.65},
  annote =	{Keywords: Graph rigidity, line configurations in 3D}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.58
Configurations of Lines in 3-Space and Rigidity of Planar Structures

Authors: Orit E. Raz

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
Let L be a sequence (l_1,l_2,...,l_n) of n lines in C^3. We define the intersection graph G_L=([n],E) of L, where [n]:={1,..., n}, and with {i,j} in E if and only if i\neq j and the corresponding lines l_i and l_j intersect, or are parallel (or coincide). For a graph G=([n],E), we say that a sequence L is a realization of G if G subset G_L. One of the main results of this paper is to provide a combinatorial characterization of graphs G=([n],E) that have the following property: For every generic realization L of G, that consists of n pairwise distinct lines, we have G_L=K_n, in which case the lines of L are either all concurrent or all coplanar. The general statements that we obtain about lines, apart from their independent interest, turns out to be closely related to the notion of graph rigidity. The connection is established due to the so-called Elekes-Sharir framework, which allows us to transform the problem into an incidence problem involving lines in three dimensions. By exploiting the geometry of contacts between lines in 3D, we can obtain alternative, simpler, and more precise characterizations of the rigidity of graphs.
Cite as

Orit E. Raz. Configurations of Lines in 3-Space and Rigidity of Planar Structures. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 58:1-58:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{raz:LIPIcs.SoCG.2016.58,
  author =	{Raz, Orit E.},
  title =	{{Configurations of Lines in 3-Space and Rigidity of Planar Structures}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{58:1--58:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.58},
  URN =		{urn:nbn:de:0030-drops-59503},
  doi =		{10.4230/LIPIcs.SoCG.2016.58},
  annote =	{Keywords: Line configurations, Rigidity, Global Rigidity, Laman graphs}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.522
Polynomials Vanishing on Cartesian Products: The Elekes-Szabó Theorem Revisited

Authors: Orit E. Raz, Micha Sharir, and Frank de Zeeuw

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
Let F in Complex[x,y,z] be a constant-degree polynomial, and let A,B,C be sets of complex numbers with |A|=|B|=|C|=n. We show that F vanishes on at most O(n^{11/6}) points of the Cartesian product A x B x C (where the constant of proportionality depends polynomially on the degree of F), unless F has a special group-related form. This improves a theorem of Elekes and Szabo [ES12], and generalizes a result of Raz, Sharir, and Solymosi [RSS14a]. The same statement holds over R. When A, B, C have different sizes, a similar statement holds, with a more involved bound replacing O(n^{11/6}). This result provides a unified tool for improving bounds in various Erdos-type problems in combinatorial geometry, and we discuss several applications of this kind.
Cite as

Orit E. Raz, Micha Sharir, and Frank de Zeeuw. Polynomials Vanishing on Cartesian Products: The Elekes-Szabó Theorem Revisited. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 522-536, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{raz_et_al:LIPIcs.SOCG.2015.522,
  author =	{Raz, Orit E. and Sharir, Micha and de Zeeuw, Frank},
  title =	{{Polynomials Vanishing on Cartesian Products: The Elekes-Szab\'{o} Theorem Revisited}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{522--536},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.522},
  URN =		{urn:nbn:de:0030-drops-51031},
  doi =		{10.4230/LIPIcs.SOCG.2015.522},
  annote =	{Keywords: Combinatorial geometry, incidences, polynomials}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.569
The Number of Unit-Area Triangles in the Plane: Theme and Variations

Authors: Orit E. Raz and Micha Sharir

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
We show that the number of unit-area triangles determined by a set S of n points in the plane is O(n^{20/9}), improving the earlier bound O(n^{9/4}) of Apfelbaum and Sharir. We also consider two special cases of this problem: (i) We show, using a somewhat subtle construction, that if S consists of points on three lines, the number of unit-area triangles that S spans can be Omega(n^2), for any triple of lines (it is always O(n^2) in this case). (ii) We show that if S is a convex grid of the form A x B, where A, B are convex sets of n^{1/2} real numbers each (i.e., the sequences of differences of consecutive elements of A and of B are both strictly increasing), then S determines O(n^{31/14}) unit-area triangles.
Cite as

Orit E. Raz and Micha Sharir. The Number of Unit-Area Triangles in the Plane: Theme and Variations. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 569-583, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{raz_et_al:LIPIcs.SOCG.2015.569,
  author =	{Raz, Orit E. and Sharir, Micha},
  title =	{{The Number of Unit-Area Triangles in the Plane: Theme and Variations}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{569--583},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.569},
  URN =		{urn:nbn:de:0030-drops-51125},
  doi =		{10.4230/LIPIcs.SOCG.2015.569},
  annote =	{Keywords: Combinatorial geometry, incidences, repeated configurations}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact