BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Orit E. Raz

Orit E. Raz appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.COComputational GeometryDiscrete Mathematicsmath.MGmath.PR

Catalog footprint

What is connected

11works
5topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

11 published item(s)

preprint2022arXiv

On the $d$-dimensional algebraic connectivity of graphs

The $d$-dimensional algebraic connectivity $a_d(G)$ of a graph $G=(V,E)$, introduced by Jordán and Tanigawa, is a quantitative measure of the $d$-dimensional rigidity of $G$ that is defined in terms of the eigenvalues of stiffness matrices (which are analogues of the graph Laplacian) associated to mappings of the vertex set $V$ into $\mathbb{R}^d$. Here, we analyze the $d$-dimensional algebraic connectivity of complete graphs. In particular, we show that, for $d\geq 3$, $a_d(K_{d+1})=1$, and for $n\geq 2d$, \[ \left\lceil\frac{n}{2d}\right\rceil-2d+1\leq a_d(K_n) \leq \frac{2n}{3(d-1)}+\frac{1}{3}. \]

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A note on distinct distances

We show that, for a constant-degree algebraic curve $γ$ in $\mathbb{R}^D$, every set of $n$ points on $γ$ spans at least $Ω(n^{4/3})$ distinct distances, unless $γ$ is an {\it algebraic helix} (see Definition 1.1). This improves the earlier bound $Ω(n^{5/4})$ of Charalambides [Discrete Comput. Geom. (2014)]. We also show that, for every set $P$ of $n$ points that lie on a $d$-dimensional constant-degree algebraic variety $V$ in $\mathbb{R}^D$, there exists a subset $S\subset P$ of size at least $Ω(n^{\frac{4}{9+12(d-1)}})$, such that $S$ spans $\binom{|S|}{2}$ distinct distances. This improves the earlier bound of $Ω(n^{\frac{1}{3d}})$ of Conlon et al. [SIAM J. Discrete Math. (2015)]. Both results are consequences of a common technical tool, given in Lemma 2.7 below.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Configurations of lines in space and combinatorial rigidity

Let $L$ be a sequence $(\ell_1,\ell_2,\ldots,\ell_n)$ of $n$ lines in $\mathbb{C}^3$. We define the {\it intersection graph} $G_L=([n],E)$ of $L$, where $[n]:=\{1,\ldots, n\}$, and with $\{i,j\}\in E$ if and only if $i\neq j$ and the corresponding lines $\ell_i$ and $\ell_j$ intersect, or are parallel (or coincide). For a graph $G=([n],E)$, we say that a sequence $L$ is a {\it 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 {\it 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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On triple intersections of three families of unit circles

Let $p_1,p_2,p_3$ be three distinct points in the plane, and, for $i=1,2,3$, let $\mathcal C_i$ be a family of $n$ unit circles that pass through $p_i$. We address a conjecture made by Székely, and show that the number of points incident to a circle of each family is $O(n^{11/6})$, improving an earlier bound for this problem due to Elekes, Simonovits, and Szabó [Combin. Probab. Comput., 2009]. The problem is a special instance of a more general problem studied by Elekes and Szabó [Combinatorica, 2012] (and by Elekes and Rónyai [J. Combin. Theory Ser. A, 2000]).

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Elekes-Szabó Theorem in four dimensions

Let $F\in\mathbb{C}[x,y,s,t]$ be an irreducible constant-degree polynomial, and let $A,B,C,D\subset\mathbb{C}$ be finite sets of size $n$. We show that $F$ vanishes on at most $O(n^{8/3})$ points of the Cartesian product $A\times B\times C\times D$, unless $F$ has a special group-related form. A similar statement holds for $A,B,C,D$ of unequal sizes. This is a four-dimensional extension of our recent improved analysis of the original Elekes-Szabó theorem in three dimensions. We give three applications: an expansion bound for three-variable real polynomials that do not have a special form, a bound on the number of coplanar quadruples on a space curve that is neither planar nor quartic, and a bound on the number of four-point circles on a plane curve that has degree at least five.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the number of unit-area triangles spanned by convex grids in the plane

A finite set of real numbers is called convex if the differences between consecutive elements form a strictly increasing sequence. We show that, for any pair of convex sets $A, B\subset\mathbb R$, each of size $n^{1/2}$, the convex grid $A\times B$ spans at most $O(n^{37/17}\log^{2/17}n)$ unit-area triangles. This improves the best known upper bound $O(n^{31/14})$ recently obtained in \cite{RS}. Our analysis also applies to more general families of sets $A$, $B$, known as sets of Szemerédi--Trotter type.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The number of unit-area triangles in the plane: Theme and variations

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 [Discrete Comput. Geom., 2010]. 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 $Ω(n^2)$, for any triple of lines (it is always $O(n^2)$ in this case). (ii) We show that if $S$ is a {\em convex grid} of the form $A\times B$, where $A$, $B$ are {\em 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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Partial-Matching and Hausdorff RMS Distance Under Translation: Combinatorics and Algorithms

We consider the RMS distance (sum of squared distances between pairs of points) under translation between two point sets in the plane, in two different setups. In the partial-matching setup, each point in the smaller set is matched to a distinct point in the bigger set. Although the problem is not known to be polynomial, we establish several structural properties of the underlying subdivision of the plane and derive improved bounds on its complexity. These results lead to the best known algorithm for finding a translation for which the partial-matching RMS distance between the point sets is minimized. In addition, we show how to compute a local minimum of the partial-matching RMS distance under translation, in polynomial time. In the Hausdorff setup, each point is paired to its nearest neighbor in the other set. We develop algorithms for finding a local minimum of the Hausdorff RMS distance in nearly linear time on the line, and in nearly quadratic time in the plane. These improve substantially the worst-case behavior of the popular ICP heuristics for solving this problem.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Polynomials vanishing on grids: The Elekes-Rónyai problem revisited

In this paper we characterize real bivariate polynomials which have a small range over large Cartesian products. We show that for every constant-degree bivariate real polynomial $f$, either $|f(A,B)|=Ω(n^{4/3})$, for every pair of finite sets $A,B\subset{\mathbb R}$, with $|A|=|B|=n$ (where the constant of proportionality depends on ${\rm deg} f$), or else $f$ must be of one of the special forms $f(u,v)=h(φ(u)+ψ(v))$, or $f(u,v)=h(φ(u)\cdotψ(v))$, for some univariate polynomials $φ,ψ,h$ over ${\mathbb R}$. This significantly improves a result of Elekes and Rónyai (2000). Our results are cast in a more general form, in which we give an upper bound for the number of zeros of $z=f(x,y)$ on a triple Cartesian product $A\times B\times C$, when the sizes $|A|$, $|B|$, $|C|$ need not be the same; the upper bound is $O(n^{11/6})$ when $|A|=|B|=|C|=n$, where the constant of proportionality depends on ${\rm deg} f$, unless $f$ has one of the aforementioned special forms. This result provides a unified tool for improving bounds in various Erd\H os-type problems in geometry and additive combinatorics. Several applications of our results to problems of these kinds are presented. For example, we show that the number of distinct distances between $n$ points lying on a constant-degree parametric algebraic curve which does not contain a line, in any dimension, is $Ω(n^{4/3})$, extending the result of Pach and de Zeeuw (2013) and improving the bound of Charalambides (2012), for the special case where the curve under consideration has a polynomial parameterization. We also derive improved lower bounds for several variants of the sum-product problem in additive combinatorics.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Sets with few distinct distances do not have heavy lines

Let $P$ be a set of $n$ points in the plane that determines at most $n/5$ distinct distances. We show that no line can contain more than $O(n^{43/52}{\rm polylog}(n))$ points of $P$. We also show a similar result for rectangular distances, equivalent to distances in the Minkowski plane, where the distance between a pair of points is the area of the axis-parallel rectangle that they span.

0 citations0 reviewsNo code linkedOpen access