Oct 27, 2008

Euclid's Elements


Today I found a very nice link on Euclid's elements.

http://aleph0.clarku.edu/~djoyce/java/elements/elements.html

Computational Geometry: Software Implementation

Computational geometry investigates algorithms for geometric problems. Motivated by the need for geometric computing in science and engineering applications that deal with the physical
world, about twenty years ago a community of researchers started forming around the study of algorithms for geometric problems. A new discipline, ‘computational geometry’, was soon
chartered with the dual mission of investigating the combinatorial structure of geometric objects and providing practical tools and techniques for the analysis and solution of fundamental
geometric problems. The inward research orientation freed computational geometers from the unpleasantness of modeling the complexity and imperfections of the physical world and of coping with the limitations of realistic computing devices. It allowed them to focus on the analysis of a simple, well-behaved, geometric objects that can be manipulated by idealized computing machines with unbounded memory space and real number arithmetic. However, at the same time as the accomplishments of computational geometers were celebrated within the general field of theory of computing, they also became less understood in applied circles. The simplifying models that enabled theoretical research to flourish turned out to be major impediments to technology transfer, and hindered computational geometry from accomplishing its mission. In particular, some apparently innocent assumptions seem to be the main problems:

• The reliance on asymptotic analysis as the ultimate gauge for estimating the performance of geometric algorithms, disregarding more practical aspects of efficiency;
• The adoption of real arithmetic, disregarding numerical finite-precision issues;
• The neglect of degenerate configurations, disregarding the difficulty of taking them into account in implementations;
•The model of uniform access to data in memory, disregarding the huge gap between the speed of main memory and disks.

Application Fields of Computational Geometry
Computational geometry enjoys two unique assets: diversity & potential to affect most forms of computing and mature algorithmic foundations. So its application field covers a multifarious area. Here I would like to mention some of them:
• Design and manufacturing: • Information systems: • Medicine and biology: • Physical sciences• Robotics: • Graphics and visualization and many more.
For this vast area of implementation, we need robust software with standardized algorithms. More on this here at Geometry in Action.

Available Software Resources

Recognizing the need for reusable and standard software, dedicated people and organizations are now working for development and collection libraries for computational geometry software,
tools and libraries.

The LEDA Library is a C++ class library that abstracts computational geometric data structures, and includes many algorithms that act on them.Computational Geometry Algorithms Library:CGAL has an initial release of its C++ class library.The contribution of CGAL and LEDA deserve a descriptive elaboration:

LEDA: Library of Efficient Data Types and Algorithms: a C++ library of the data types and algorithms of combinatorial computing. It provides a large collection of data types and algorithms in a form that can be used by non-experts. Several geometric algorithms including convex hulls and line segment intersection are included here.

CGAL: Computational Geometry Algorithm Library: It provides easy access to its resources. It offers data structures and algorithms like Voronoi diagrams, Boolean operations on polygons
and polyhedra, arrangements of curves and their applications, mesh generation, geometry processing, convex hull algorithms, operations on polygons, search structures, shape analysis,
fitting, and distances, kinetic data structures etc. All these data structures and algorithms operate on geometric objects like points and segments. These objects and predicates are regrouped in CGAL Kernels. The codes are basically written in C++.

Some notable people engaged in this mission are:
• Nina Amenta: Has collected a large number of free computational geometry programs arranged by subject.
Seth Teller: He has a collection of C code and SGI executables for linear programming, voronoi diagrams, and manipulation of NURBS surfaces.
Joe O’Rourke: He made C code corresponding to the material in his textbook, ‘Computational Geometry in C’.


Application Challenges

To build an effective pipeline connecting theory to practice Computational Geometer must start thinking not only in terms of asymptotic complexity, but also about:
• Code robustness • CPU times • Standard and Benchmark
• Precisions • Distribution
More on this can be found in this report.
In geometric computing, software libraries consisting of reliable components are particularly useful, since implementers of geometric algorithms are faced with notoriously difficult problems, especially the problems of robustness and degeneracies. Therefore, we need programs that run efficiently and robustly so that it can generate same output on different platforms. Reusable and maintainable data structures are also necessary.

Some other nice links:
http://www.personal.kent.edu/~rmuhamma/Compgeometry/compgeom.html
http://3dpancakes.typepad.com/ernie/
http://compgeom.cs.uiuc.edu/~jeffe/compgeom/
http://www.ics.uci.edu/~eppstein/geom.html

Oct 23, 2008

Voronoi Diagram

Voronoi diagrams are wonderful geometric shapes , the more I learn about them, the more fascinated I become. These shapes are inherent in nature, we can see examples of Voronoi regions around us. But first let me explain in my own words about Voronoi diagrams.

Let us take some point sites in a plane. Now our task is to divide the total space into convex polygons or regions surrounding the sites in such a way that , all the points inside the polygon surrounding a site will be closer to that site than any other site of the plane. The diagram we get this way is our desired Voronoi diagram.



Seems a simple one to think. If we restrict the problem in a way that instead of polygon we have to draw circles, then we just take point circles centering the sites and increase their radii until they intersect any other circle. This way each circle contains points that are closer to their centre than any other circle in the plain. But there will be many point that will not be included in any of the circles, so now we have to think about polygon so that all the points will belong to a polygon, no points left aside.

Suppose, we have a set of stars and planets. Now we have to find out which planet belong to which star. If we draw the Voronoi diagram considering the stars as the pint sites then we get the space partitioned with polygons.






If a planet falls inside a polygon P that contains star S, then certainly the planet revolves around S as it is closer to this star than any other star of the constellation. The gravitic field of S is stronger onto the planet than any other star.

Voronoi diagrams have widespread applications in areas such as computer graphics, epidemiology, geophysics, and meteorology. A particularly notable use of a Voronoi diagram was the analysis of the 1854 cholera epidemic in London, in which physician John Snow determined a strong correlation of deaths with proximity to a particular (and infected) water pump on Broad Street.-mathworld

Voronoi diagram in Dragon fly wing
Voronoi Diagram in modern art

Differentiated Surveillance with Wireless Sensor Network

In computer science and telecommunications, wireless sensor networks are an active research area with numerous workshops and conferences arranged each year. And a bigger part of this
research is focused on how the energy consumption can be reduced further. Networks where nodes are heterogeneous and the coverage requirements are also different for nodes, we can exploit this feature to obtain a lower energy usage there. A wireless sensor network (WSN) is a wireless network consisting of spatially distributed autonomous devices using sensors to
cooperatively monitor physical or environmental conditions, such as temperature, sound, vibration, pressure, motion or pollutants, at different locations. The development of wireless sensor networks was originally motivated by military applications such as battlefield surveillance. However, wireless sensor networks are now used in many civilian application areas, including environment and habitat monitoring, health care applications, home automation, and traffic control.

Sensor Network:
A sensor is a device the produces a measurable response to a change in physical condition such as temperature or chemical condition such as concentration, like temperature sensor, humidity
sensor etc.

Specialty and Difference of Sensor Network:
Network topology is not fixed in sensor networks. Power is an expensive resource in these networks Nodes are connected by wireless links and a large number of sensors are deployed.
Addressing scheme for sensor nodes are also different from ad-hoc networks. Sensor network is used for data aggregation where data flow from multiple sources to a single destination. There
can generally be huge amount of redundancy in data traffic. The bigger problem is sensor nodes are prone to failure very often.

Energy Aware Routing:
Energy saving is crucial for sensornets. Network lifetime depends on energy management policy. Communication is the most expensive activity. To maintain an energy aware routing schedule, possible goals include:
• Lowest energy route
• Route via highest available energy
• Distribute energy burden evenly
• Lowest routing overhead.
To reduce energy consumption, Destination Initiated Routing is performed. A directional flooding is followed that determine various routes (based on location).The energy metrics are
collected along the way where every route has a probability of being chosen which is inversely proportional to its energy cost. The choice of path is made locally at every node for every packet.

Differentiated Surveillance:
Sensornets are used for surveillance in many areas. Environmental hazard exploration, Military tracking, Battle fields, Earthquake response, Biomedicine 2etc are some of them. Human presence is risky in these cases, so wireless sensor is used instead. Different areas or situation may need different degree of coverage, for example: Security sensitive area, areas susceptible to environmental hazards, in case of biomedicine, more risk prone areas etc. By differentiated surveillance, we indicate providing different degrees of sensing coverage for different nodes.

Oct 19, 2008

Download Books by Isaac Asimov: Foundation and Robot Series

The Robot series:

The complete robot
The Caves of Steel
The Robots of Dawn
Robots and Empire



The Foundation series:

Prelude to Foundation
Forward the Foundation
The Foundation Trilogy [
Foundation - Foundation and Empire - Second Foundation]
Foundation's Edge
Foundation and Earth


Eid 2008

The Eid day was boring as usual , but the get together party after a day after Eid was awesome..a wonderful reunion of old friends. After reaching Shefali's home i took the place from where i van see the door well ..so whenever a person came I declared her presence...'now comes Shumi...!!!'...and another splash of laughter , sometimes fake and sometimes real...at least we could laugh loud.

Oct 6, 2008

flaw in the Internet's Domain Name System

How a recently discovered flaw in the Internet's Domain Name System makes it easy for scammers to lure you to fake Web sites.
The Domain Name System is essentially the Internet's phone book. It's a huge database containing the 32‑bit numeric codes that identify every single site on the Internet. These are known as Internet Protocol addresses, or IP addresses for short. Amazingly, this database is distributed over some 12 million computers worldwide, known as DNS name servers.

read more


DNS checker: To find out if the DNS server you use is vulnerable : http://www.doxpara.com/

The United States Computer Emergency Readiness Team (US-CERT) logs this problem in their vulnerability note : Multiple DNS implementations vulnerable to cache poisoning. They say about the impact of this flaw: 'An attacker with the ability to conduct a successful cache poisoning attack can cause a nameserver's clients to contact the incorrect, and possibly malicious, hosts for particular services. Consequently, web traffic, email, and other important network data can be redirected to systems under the attacker's control. '