# 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 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. 2016 Siam Journal on Discrete Mathematics 30 (2), pp. 934 - 954 (21) London South Bank University doi:10.1137/16M1059412 12 May 2016 24 May 2016 01 Mar 2016 kleinSIDMA.pdfLicenseCC BY-ND

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

total views
• ##### 2
views this month

## Related outputs

##### 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
##### 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
##### Rigid Body Dynamics using Equimomental Systems of Point-Masses
Selig, J. and Laus, L. (2019). Rigid Body Dynamics using Equimomental Systems of Point-Masses. Acta Mechanica.
##### 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.