About this site
The SIG Algorithm
Applications of SIG
The demonstration applet
References on SIG

About the SIG

In computer vision applications, low-level vision has been studied extensively- a grey level intensity array of a visual pattern or scene. One class of patterns or scenes that receive considerable attention are dot patterns. Human observers perceive the shape of such sets of dots quite easily. Several methods have been studied in literature to duplicate this ability, or automate it, using the minimum spanning tree, relative neighborhood graph, alpha-hulls etc. However, most methods suffer from some drawback or the other- computational ineffeciency, lack of elegance or dependency on tuning of parameters involved.

The Spheres-of-Influence graph is one method that does not suffer from such drawbacks. In particular, the SIG

  • outputs the shape of the dot pattern as a function of what the data looks like.
  • gives either a connected graph or a set of disconnected components where appropriate.
  • does all this without requiring any tuning of parameters.
  • can be effeciently computed.

About this website

This website was designed with an interactive Java applet for demonstrating the concept of the Sphere-of-Influence graph. This site was created to fulfill the partial requirements of the course COMP 507, Computational Geometry, taught by Professor Godfried T. Toussaint at the McGill University School of Computer Science (SOCS).

About the website author

My name is Junaed Sattar, and I did this website during my second year at the Master's program at McGill SOCS, taking Professor Toussaint's Computational Geometry course. I'd like mention here Richard Unger's SIG applet, which was an inspiration and guide for my own applet. The applet source will be available soon; look for it in the applet page.

If you like to contact me, please send email at jsatta AT cs DOT mcgill DOT ca (yes,fellow human being, I know you can read my email address comfortably, but not you, evil spambots!). Feedback is always welcome. If you ever want to meet me in person, I live in the beautiful city of Montreal, and most of the time I'm in Professor Dudek's (who happens to be my supervisor) Mobile Robotics Lab, at McConell Engineering building, room 416, McGill University.