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). https://doi.org/10.1137/16M1059412
AuthorsRudnev, 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.

Year2016
JournalSiam Journal on Discrete Mathematics
Journal citation30 (2), pp. 934 - 954 (21)
PublisherSociety for Industrial and Applied Mathematics
ISSN0895-4801
Digital Object Identifier (DOI)https://doi.org/10.1137/16M1059412
Publication dates
Print12 May 2016
Publication process dates
Deposited24 May 2016
Accepted01 Mar 2016
Publisher's version
License
File Access Level
Open
Permalink -

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

Download files


Publisher's version
kleinSIDMA.pdf
License: CC BY-ND
File access level: Open

  • 122
    total views
  • 195
    total downloads
  • 0
    views this month
  • 0
    downloads this month

Export as

Related outputs

Mechanisms Generating Line Trajectories
Selig, J. and Di Paola, V. (2023). Mechanisms Generating Line Trajectories. Mechanism and Machine Theory. 191, p. 105494.
Playing with Quaternions and Dual Quaternions -- Clifford algebras in Game Development
Selig, J. and Todd, H.P. (2023). Playing with Quaternions and Dual Quaternions -- Clifford algebras in Game Development. Mathematics Today.
Kinematics from the Active Point of View
Selig, J. (2023). Kinematics from the Active Point of View. in: Ang Jr., M. H., Khatib, O. and Siciliano, B. (ed.) Encyclopedia of Robotics Springer.
Points in the Plane, Lines in Space
Selig, J.M. (2022). Points in the Plane, Lines in Space. Journal of Geometry. https://doi.org/10.1007/s00022-022-00661-3
Line-Point Constraints and Robot Surgery
Selig, J.M. (2022). Line-Point Constraints and Robot Surgery. 18th International Symposium on Advances in Robot Kinematics. Bilbao, Spain 30 Mar - 26 Jun 2022 Springer.
On the Geometry of Some Localisation Problems in Robotics
Selig, J.M. On the Geometry of Some Localisation Problems in Robotics. 2nd IMA Conference on the Mathematics of Robotics. Online 08 - 10 Sep 2021 Springer.
Synthesis of Planar Stiffness
Selig, J. M. (2021). Synthesis of Planar Stiffness. 2nd IMA Conference on the Mathematics of Robotics. Online 08 - 10 Sep 2021 Society for Industrial and Applied Mathematics.
On Plane-Symmetric Rigid-Body Motions
Bayril, D. and Selig, J. (2020). On Plane-Symmetric Rigid-Body Motions. Journal of Geometry. 111 (29). https://doi.org/10.1007/s00022-020-00543-6
On the Plane Symmetric Bricard Mechanism
Selig, J. (2020). On the Plane Symmetric Bricard Mechanism. Lenarčič, J. and Siciliano, B. (ed.) 17 International Symposium on Advances in Robot Kinematics. Ljubljana, Slovenia 28 Jun - 02 Jul 2020 Springer. https://doi.org/10.1007978-3-030-50975-0_10
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. https://doi.org/10.1016/j.cagd.2020.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. https://doi.org/10.1007/s00707-019-02543-3
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 https://doi.org/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 https://doi.org/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 Institute of Electrical and Electronics Engineers (IEEE). https://doi.org/10.1109/REMAR.2018.8449894
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 Springer. https://doi.org/10.1007/978-3-319-93188-3_4
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. pp. 77 - 85 (9)
Mobile Icosapods
Gallet, M, Nawratil, G, Schicho, J and Selig, JM (2017). Mobile Icosapods. Advances in Applied Mathematics. 88 (July), pp. 1-25. https://doi.org/10.1016/j.aam.2016.12.002
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 Springer. https://doi.org/10.1007/978-3-319-60867-9_53
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. https://doi.org/10.1137/16M1090971
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, Information 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.
Some mathematical problems in robotics
Selig, JM (2000). Some mathematical problems in robotics. School of Computing, Information Systems and Mathematics, South Bank University, London.
Introduction to Polynomial Invariants of Screw Systems
Donelan, P and Selig, JM (2007). Introduction to Polynomial Invariants of Screw Systems. arXiv.
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 https://doi.org/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. pp. 147 - 154
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. https://doi.org/10.1243/0954406021524927
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.
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). https://doi.org/10.1109/TRO.2015.2426471
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. https://doi.org/10.1007/s00022-016-0331-5
Some Mobile Overconstrained Parallel Mechanisms
Selig, JM (2016). Some Mobile Overconstrained Parallel Mechanisms. Advances in Robot Kinematics. Grasse, France 27 - 30 Jun 2016
Rational interpolation of car motions
Selig, JM (2015). Rational interpolation of car motions. Journal of Mechanisms and Robotics. 7 (3). https://doi.org/10.1115/1.4030298
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 Institute of Mathematics and its Applications (IMA). pp. ? - ? (8)
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. https://doi.org/10.1007/s00707-014-1103-7
Some rational vehicle motions
Selig, JM (2013). Some rational vehicle motions. in: Computational Kinematics Proceedings of the 6th International Workshop on Computational Kinematics (CK2013) Springer. pp. 21-29
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. https://doi.org/10.1017/S026357471300026X
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. https://doi.org/10.1016/j.mechmachtheory.2010.10.001
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. https://doi.org/10.1016/j.mechmachtheory.2011.05.001
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. https://doi.org/10.1007/s10440-011-9634-6
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. https://doi.org/10.1007/s00006-008-0144-1
Quadratic constraints on rigid-body displacements
Selig, JM (2010). Quadratic constraints on rigid-body displacements. Journal of Mechanisms and Robotics. 2 (4). https://doi.org/10.1115/1.4002344
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. https://doi.org/10.1007/s00006-010-0229-5
Manipulating robots along helical trajectories
Selig, JM and Ovseevitch, AI (2009). Manipulating robots along helical trajectories. Robotica. 14 (3), pp. 261-267. https://doi.org/10.1017/S0263574700019573
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. https://doi.org/10.1115/1.3063630
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 Institute of Electrical and Electronics Engineers (IEEE). pp. 2380 - 2385 https://doi.org/10.1109/ROBOT.2008.4543569
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. https://doi.org/10.1093/imamci/dnl017
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. https://doi.org/10.1109/MRA.2006.1598057
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 Institute of Electrical and Electronics Engineers (IEEE). pp. 1086 - 1091 https://doi.org/10.1109/IROS.2006.281815
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 Institute of Electrical and Electronics Engineers (IEEE). https://doi.org/10.1109/ROBOT.2005.1570617
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. https://doi.org/10.1016/j.ijmecsci.2004.05.009
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.
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 Institute of Electrical and Electronics Engineers (IEEE). https://doi.org/10.1109/IROS.2001.973376
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 Institute of Electrical and Electronics Engineers (IEEE). https://doi.org/10.1109/IROS.2001.976395
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 Institute of Electrical and Electronics Engineers (IEEE). https://doi.org/10.1109/ROBOT.2000.845218
Clifford algebra of points, lines and planes
Selig, JM (2000). Clifford algebra of points, lines and planes. Robotica. 18 (5), pp. 545 - 556. https://doi.org/10.1017/S0263574799002568