# On the use of the Klein quadric for geometric incidence problems in two dimensions

Journal article

Rudnev, M and Selig, JM (2016). On the use of the Klein quadric for geometric incidence problems in two dimensions.

*Siam Journal on Discrete Mathematics.*30 (2), pp. 934 - 954 (21).

Authors | Rudnev, M and Selig, JM |
---|---|

Abstract | We discuss a unified approach to a class of geometric combinatorics incidence problems in two dimensions, of the Erdös distance type. The goal is obtaining the second moment estimate. That is, given a finite point set $S$ in two dimensions, and a function $f$ on $S\times S$, find the upper bound for the number of solutions of the equation $f(p,p') = f(q,q')\neq 0, (p,p',q,q')\in S\times S\times S\times S$; e.g., $f$ is the Euclidean distance in the plane, sphere, or a sheet of the two-sheeted hyperboloid. Our ultimate tool is the Guth--Katz incidence theorem for lines in $\mathbb{RP}^3$, but we focus on how the original problem in two dimensions gets reduced to its application. The corresponding procedure was initiated by Elekes and Sharir, based on symmetry considerations. The point we make here is that symmetry considerations, not necessarily straightforward and potentially requiring group representation machinery can be bypassed or made implicit. The classical Plücker--Klein formalism for line geometry enables one to directly interpret a solution to the above relation as an intersection of two lines in $\mathbb{RP}^3$. This, e.g., allows for a very brief argument as to how the Euclidean plane distance argument extends to the spherical and hyperbolic distances. The space of lines in the projective three-space, the Klein quadric $\mathcal K$, is four dimensional. Thus, we start out with an injective map $\mathfrak F:\,S\times S\to\mathcal K$, that is from a pair of points $(p,q)$ to a line $l_{pq}$ and seek a corresponding combinatorial problem in the above form in two dimensions, which can be solved by applying the Guth--Katz theorem to the set of lines $\{l_{pq}\}$ in $\mathbb{RP}^3$. We identify a few arguably new such problems, and hence applications of the Guth--Katz theorem and make generalizations of the existing ones. It is the dimension of the direct approach in question that is the main purpose of this paper. |

Year | 2016 |

Journal | Siam Journal on Discrete Mathematics |

Journal citation | 30 (2), pp. 934 - 954 (21) |

Publisher | London South Bank University |

Digital Object Identifier (DOI) | doi:10.1137/16M1059412 |

Publication dates | |

Print | 12 May 2016 |

Publication process dates | |

Deposited | 24 May 2016 |

Accepted | 01 Mar 2016 |

Publisher's version | License CC BY-ND |

https://openresearch.lsbu.ac.uk/item/87422

##### 9

total views##### 39

total downloads##### 0

views this month##### 2

downloads this month

## Related outputs

##### Another Map from P^7 to the Study Quadric

Selig, Jon (2020). Another Map from P^7 to the Study Quadric.*Computer Aided Geometric Design.*77, p. 101816.

##### Rigid Body Dynamics using Equimomental Systems of Point-Masses

Laus, L. and Selig, J. (2019). Rigid Body Dynamics using Equimomental Systems of Point-Masses.*Acta Mechanica.*pp. 1-16.

##### Parallel Robots with Homokinetic Joints:The Zero-Torsion Case

Wu, Y, Selig, J and Carricato, M (2019). Parallel Robots with Homokinetic Joints:The Zero-Torsion Case.*15th IFToMM World Congress.*Krakov, Poland 30 Jun - 04 Jul 2019 doi:10.1007/978-3-030-20131-9_27

##### On the Dynamics of a Ball Rolling on a Tipping Plane

Laus, LP and Selig, JM (2019). On the Dynamics of a Ball Rolling on a Tipping Plane.*15th IFToMM World Congress,.*Krakov, Poland, 30 Jun - 04 Jul 2019 doi:10.1007/978-3-030-20131-9_194

##### Double Bennett Mechanisms with Assembly Modes of Different Dimensions

Selig, JM and Li, Z (2018). Double Bennett Mechanisms with Assembly Modes of Different Dimensions.*4th International Conference on Reconfigurable Mechanisms and Robots.*Delft 20 - 22 Jun 2018 London South Bank University.

##### Displacement Varieties for Some PUP Linkages

Selig, JM (2018). Displacement Varieties for Some PUP Linkages.*16th International Symposium on Advances in Robot Kinematics.*Bologna, Italy 01 - 05 Jul 2018

##### Hyperbolic pseudoinverses for kinematics in the Euclidean group

Selig, JM (2017). Hyperbolic pseudoinverses for kinematics in the Euclidean group.*SIAM Journal on Matrix Analysis and Applications.*38 (4), pp. 1541-1559.

##### Some rational vehicle motions

Selig, JM (2013). Some rational vehicle motions.*6th International Workshop on Computational Kinematics (CK2013).*Barcelona, Spain 12 - 15 May 2013 London South Bank University. doi:10.1007/978-94-007-7214-4-3

##### Equimomental systems and robot dynamics

Selig, JM (2015). Equimomental systems and robot dynamics.*IMA Conference on Mathematics of Robotics.*St Anne’s College, University of Oxford 09 - 11 Sep 2015 London South Bank University. pp. ? - ? (8)

##### Manipulating robots along helical trajectories

Selig, JM and Ovseevitch, AI (2009). Manipulating robots along helical trajectories.*Robotica.*14 (3), pp. 261-267.

##### Motion Interpolation in Lie Subgroups and Symmetric Subspaces

Selig, JM, Wu, Y and Carricato, M (2017). Motion Interpolation in Lie Subgroups and Symmetric Subspaces.*7th IFToMM International Workshop of Computational Kinematics.*Futurescope, Poitiers, France 22 - 24 May 2017 London South Bank University. doi:http://doi.org/10.1007/978-3-319-60867-9_53

##### Some Remarks on the RRR Linkage

Selig, JM (2014). Some Remarks on the RRR Linkage. in: Lenarcic, J and Khatib, O (ed.) Advances in robot kinematics: analysis and design Switzerland Springer International Publishing. pp. 77 - 85 (9)##### Some Mobile Overconstrained Parallel Mechanisms

Selig, JM (2016). Some Mobile Overconstrained Parallel Mechanisms.*Advances in Robot Kinematics.*Grasse, France 27 - 30 Jun 2016 London South Bank University.

##### The complex of lines from successive points and the horopter

Selig, JM (2008). The complex of lines from successive points and the horopter.*IEEE International Conference on Robotics and Automation.*California 19 - 23 May 2008 London South Bank University. pp. 2380 - 2385 doi:10.1109/ROBOT.2008.4543569

##### A screw theory of static beams

Selig, JM and Ding, X (2001). A screw theory of static beams.*IEEE International Conference on Intelligent Robots and Systems.*San Diego, CA, USA 29 Oct - 03 Nov 2001 London South Bank University. doi:10.1109/IROS.2001.973376

##### Mobile Icosapods

Gallet, M, Nawratil, G, Schicho, J and Selig, JM (2017). Mobile Icosapods.*Advances in Applied Mathematics.*88 (July), pp. 1-25.

##### Note on the Principle of Transference

Selig, JM (1986). Note on the Principle of Transference.*Design Engineering Technical Conference.*Columbus, Ohio London South Bank University.

##### Scaling Direct Drive Robots

Wallace, R and Selig, JM (1995). Scaling Direct Drive Robots.*Robotics and Automation, 1995 IEEE International Conference on.*Nagoya, Japan 21 - 27 May 1995 Wallace.

##### Clifford algebra of points, lines and planes

Selig, JM (1999).*Clifford algebra of points, lines and planes.*London South Bank University School of Computing, Infromations Systems and Mathematics, South Bank University, London.

##### Some remarks on the statistics of pose estimation

Selig, JM (2000).*Some remarks on the statistics of pose estimation.*School of Computing, Information Systems and Mathematics, South Bank University, London.

##### Spatial stiffness matrix from simple stretched springs

Selig, JM (2000). Spatial stiffness matrix from simple stretched springs.*IEEE International Conference on Robotics & Automation.*San Francisco Ca. USA 24 - 28 Apr 2000 London South Bank University. doi:10.1109/ROBOT.2000.845218

##### Some mathematical problems in robotics

Selig, JM (2000).*Some mathematical problems in robotics.*School of Computing, Information Systems and Mathematics, South Bank University, London.

##### Theory of vibrations in Stewart platforms

Selig, JM and Ding, X (2001). Theory of vibrations in Stewart platforms.*IEEE International Conference on Intelligent Robots and Systems.*San Diego, CA USA London South Bank University. doi:10.1109/IROS.2001.976395

##### Interpolated rigid-body motions and robotics

Selig, JM and Yuanqing, W (2006). Interpolated rigid-body motions and robotics.*Proceedings of the 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems.*Beijing, China 09 - 15 Oct 2006 London South Bank University. pp. 1086 - 1091 doi:10.1109/IROS.2006.281815

##### Introduction to Polynomial Invariants of Screw Systems

Donelan, P and Selig, JM (2007).*Introduction to Polynomial Invariants of Screw Systems.*arXiv.

##### Clifford algebra of points, lines and planes

Selig, JM (2000). Clifford algebra of points, lines and planes.*Robotica.*18 (5), pp. 545 - 556.

##### Centrodes and Lie algebra

Selig, JM (2007). Centrodes and Lie algebra.*2th IFT oMM World Congress.*Besancon France 18 - 21 Jun 2007 London South Bank University. pp. ? - ? (6)

##### Cayley maps for SE(3)

Selig, JM (2007). Cayley maps for SE(3).*12th International Federation for the Promotion of Mechanism and Machine Science World Congress.*Besancon France London South Bank University. pp. ? - ? (6)

##### A geometric Newton-Raphson method for Gough-Stewart platforms

Selig, JM and Li, H (2009). A geometric Newton-Raphson method for Gough-Stewart platforms.*Fifth International Workshop on Computational Kinematics.*University of Duisburg-Essen, Germany 06 - 08 May 2009 London South Bank University. pp. 183 - 190 doi:10.1007/978-3-642-01947-0_23

##### Some rigid-body constraint varieties generated by linkages

Selig, JM (2012). Some rigid-body constraint varieties generated by linkages. in: Lenarcic, J and Husty, M (ed.) Latest Advances in Robot Kinematics Dordrecht Springer.##### A screw syzygy with applications to robot singularity computation

Selig, JM and Donelan, P (2008). A screw syzygy with applications to robot singularity computation. in: Advances in Robot Kinematics: Analysis and Design Netherlands Springer Science+Business Media B.V. pp. 147 - 154##### Dynamics of vibratory bowl feeders

Selig, JM and Dai, JS (2005). Dynamics of vibratory bowl feeders.*Proceedings of the 2005 IEEE International Conference on Robotics and Automation April 2005.*Barcelona, Spain Apr 2005 London South Bank University. doi:10.1109/ROBOT.2005.1570617

##### Active versus passive transformations in robotics

Selig, JM (2006). Active versus passive transformations in robotics.*IEEE Robotics and Automation Magazine.*13 (1), pp. 79 - 84.

##### Structure of the spatial stiffness matrix

Selig, JM and Ding, X (2002). Structure of the spatial stiffness matrix.*International Journal of Robotics and Automation.*17 (1), pp. 1 - 16.

##### Diagonal spatial stiffness matrices

Selig, JM and Ding, X (2002). Diagonal spatial stiffness matrices.*International Journal of Robotics and Automation.*17 (2), pp. 100 - 106.

##### Three problems in robotics

Selig, JM (2002). Three problems in robotics.*Symposium Commemorating the Legacy, Works, and Life of Sir Robert Stawell Ball.*University of Cambridge 09 - 11 Jul 2000 London South Bank University. doi:10.1243/0954406021524927

##### Exponential and cayley maps for dual quaternions

Selig, JM (2010). Exponential and cayley maps for dual quaternions.*Advances in Applied Clifford Algebras.*20 (3-4), pp. 923 - 936.

##### Half-turns and line symmetric motions

Selig, JM and Husty, M (2011). Half-turns and line symmetric motions.*Mechanism and Machine Theory.*46 (2), pp. 156 - 167.

##### On the instantaneous acceleration of points in a rigid body

Selig, JM (2011). On the instantaneous acceleration of points in a rigid body.*Mechanism and Machine Theory.*46 (10), pp. 1522 - 1535.

##### On the geometry of point-plane constraints on rigid-body displacements

Selig, JM (2011). On the geometry of point-plane constraints on rigid-body displacements.*Acta Applicandae Mathematicae.*116 (2), pp. 133 - 155.

##### Characterisation of Frenet-Serret and Bishop motions with applications to needle steering

Selig, JM (2013). Characterisation of Frenet-Serret and Bishop motions with applications to needle steering.*Robotica.*31 (6), pp. 981 - 992.

##### On the compliance of coiled springs

Ding, X and Selig, JM (2004). On the compliance of coiled springs.*International Journal of Mechanical Sciences.*46 (5), pp. 703 - 727.

##### Curves of stationary acceleration in SE(3)

Selig, JM (2007). Curves of stationary acceleration in SE(3).*IMA Journal of Mathematical Control and Information.*24 (1), pp. 95 - 113.

##### A screw theory of Timoshenko beams

Selig, JM and Ding, X (2009). A screw theory of Timoshenko beams.*Journal of Applied Mechanics, Transactions ASME.*76 (3), pp. 1 - 7.

##### Rigid body dynamics using Clifford algebra

Selig, JM and Bayro-Corrochano, E (2010). Rigid body dynamics using Clifford algebra.*Advances in Applied Clifford Algebras.*20 (1), pp. 141 - 154.

##### On the geometry of the homogeneous representation for the group of proper rigid-body displacements

Selig, JM (2013). On the geometry of the homogeneous representation for the group of proper rigid-body displacements.*Romanian Journal of Technical Sciences - Applied Mechanics.*58 (1-2), pp. 5 - 28.

##### Rational interpolation of car motions

Selig, JM (2015). Rational interpolation of car motions.*Journal of Mechanisms and Robotics.*7 (3).

##### Quadratic constraints on rigid-body displacements

Selig, JM (2010). Quadratic constraints on rigid-body displacements.*Journal of Mechanisms and Robotics.*2 (4).

##### On the line geometry of rigid-body inertia

Selig, JM and Martins, D (2014). On the line geometry of rigid-body inertia.*Acta Mechanica.*225 (11), pp. 3073 - 3101.

##### A Class of Explicitly Solvable Vehicle Motion Problems

Selig, JM (2015). A Class of Explicitly Solvable Vehicle Motion Problems.*IEEE Transactions on Robotics.*31 (3), pp. 766 - 777 (11).

##### Persistent rigid-body motions and Study's "Ribaucour" problem

Selig, JM and Carricato, M (2016). Persistent rigid-body motions and Study's "Ribaucour" problem.*Journal of Geometry.*108 (1), pp. 149-169.