I am looking to make efficient algorithms for those vector GIS operation that take a long time for GIS software like Arc-GIS, Grass etc. I have considered polygon overlay but looking for other operations as well.
Of the top of my head, some non trivial vector operations:
- Generate a polygon layer from a GRID / DEM / RASTER
- Build a triangular irregular network from a GRID / DEM
- Functions on large datasets (buffer, generalize, reproject, check topology)
- Build / Rebuild spatial indexes on a vector layer
- GIS Analysis (Hill shade, flood map)
I'm not exactly sure what the question is, but if you're looking for complex geometry operations to implement by yourself, there are many sources for those. You could start by reading http://en.wikipedia.org/wiki/Computational_geometry#Problem_classes.
- Computational Geometry Pages
- Computational Geometry: Algorithms and Applications (book) - more theoretical, but highly recommended
- Computational Geometry in C (book) - more practical (includes quite a lot of source code), also highly recommended
In GRASS GIS 7 the vector algorithms have been significantly improved for speed, consumption of computational resources and especially the possibility to analyze huge datasets (where most other GIS fail).
To make a performance test, download the CORINE vector data from EEA and reconstruct the topology.
You've got a lot of suggestions already so I won't repeat anything except to add one obvious option and another slightly "left-field" thing-to-try.
The obvious option is to go down the route of multiprocessesing (depending on exactly what your problem is). Ignore any statements about how ArcGIS is/was single threaded etc. That is irrelevant. Spawn multiple subprocesses and use a queue to feed them. I have done this successfully with ArcGIS and GGDAL/OGR (but never tried it in GRASS) and even had a single ArcGIS licence running (with a bit of help) on a bank of networked computers in a geoprocessing farm. However, don't overload your machine. You'll need to gauge how intense any one process is and you might only get one per core (excessive subprocesses can actually result in you INCREASING the overall processing time if you're not careful) and you should leave some spare capacity for the operating system to do its stuff too. How many you can run depends a lot on your use-case and hardware.
The "slightly left-field" option is to re-think how you are accessing your geometry. This might or might not be relevant (I can't tell from your question). However, if you are using cursors to loop through your features and then more cursors to loop through your geometry, this can be slow. Under some circumstances, dumping the geometry into a container in one go can save a few milliseconds per operation and if you have hundreds of thousands of features, that can equate to time worth saving. OGR can help here. ArcPy is not so helpful for this approach.
If you need to squeeze more speed out of the set-up, think laterally about your algorithm. In GIS there is never a single correct way to do geoprocessing and alternative modules or re-ordering calculations can give good results. One simple example of lateral thinking is so obvious it is hardly worth mentioning but is often forgotten, viz. do you really need that 13 decimal place resolution in your data? A simplification pass before you start can give a real boost.
Finally, check your spatial indexing. ArcGIS is pretty good at this usually but some other databases like SpatiaLite, you need to explicitly tell it to use R-trees. On that note: your choice of database can also impact your speed.