CTK Exchange
Front Page
Movie shortcuts
Personal info
Reciprocal links
Terms of use
Privacy Policy

Interactive Activities

Cut The Knot!
MSET99 Talk
Games & Puzzles
Eye Opener
Analog Gadgets
Inventor's Paradox
Did you know?...
Math as Language
Things Impossible
My Logo
Math Poll
Other Math sit's
Guest book
News sit's

Recommend this site

Manifesto: what CTK is about Search CTK Buying a book is a commitment to learning Table of content Products to download and subscription Things you can find on CTK Chronology of updates Email to Cut The Knot Recommend this page

CTK Exchange

Subject: "Squares on a plane"     Previous Topic | Next Topic
Printer-friendly copy     Email this topic to a friend    
Conferences The CTK Exchange This and that Topic #771
Reading Topic #771
Jun-13-07, 09:47 AM (EST)
"Squares on a plane"
   There are N points (x, y). Some four points form a square. And there can be a lot of squares. Is there any algorithm which would find out how many squares are in the given set of points?

  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
Jun-17-07, 07:59 AM (EST)
1. "RE: Squares on a plane"
In response to message #0
   Firstly it is extreme improbable almost impossible that taken randomly a finite set of points in a given plane a quadruplet of them form a square. For instance suppose you have been luckily enough to obtain already three points forming two of the sides of our elusive square among all the remaining of points in the plane just one will form the square, so it is quite obvious that probability is mathematically zero.

However having said that, in case you know beforehand that somebody for instance has selected the N points so there is a quadruplet that form an square,
I outline below a procedure that will help you to discover the quadruplet without excessive work provides that you have a computer handy and some programming skills. The procedure is based on the following facts:

1) Expressing the coordinates of our N points in complex notation we get N different complex numbers.

2) Obviously our quadruplet points forming the square, lets call them Z1, Z2, Z3, Z4, have to belong to the same circumference and for that reason the cross ratio of our number (Z1 Z2 Z3 Z4) first it has to be a real number and second its value has to be -1 harmonic ratio if the two first chosen points were diagonally opposed or otherwise has to value 2 or 1/2, since for symmetry there are only three different values for the cross ratio out of the customary six values.

3) So using loops in programming you check every possible quadruplet for cross ratio, first discarding before those quadruplets which cross ratio it is not real, second selecting those which their cross ratio value is 2 ; 1/2 or -1

  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top

Conferences | Forums | Topics | Previous Topic | Next Topic

You may be curious to have a look at the old CTK Exchange archive.
Please do not post there.

Copyright © 1996-2018 Alexander Bogomolny