1995
- Mohan Kankanhalli and Wm Randolph Franklin.
Area and perimeter computation of the union of a set of iso-rectangles in parallel.
J. Parallel Distrib. Comput., 27(2):107–117, June 1995.
doi:https://doi.org/10.1006/jpdc.1995.1076.
[details] [full text]
Abstract
Finding the area and perimeter of the union/intersection of a set of iso-rectangles is a very important part of circuit extraction in VLSI design. We combine two techniques, the uniform grid and the vertex neighborhoods, to develop a new parallel algorithm for the area and perimeter problems which has an average linear time performance but is not worst-case optimal. The uniform grid technique has been used to generate the candidate vertices of the union or intersection of the rectangles. An efficient point-in-rectangles inclusion test filters the candidate set to obtain the relevant vertices of the union or intersection. Finally, the vertex neighborhood technique is used to compute the mass properties from these vertices. This algorithm has an average time complexity of O(((n + k)/p) + log p) where n is the number of input rectangle edges with k intersections on p processors assuming a PRAM model of computation. The analysis of the algorithm on a SIMD architecture is also presented. This algorithm requires very simple data structures which makes the implementation easy. We have implemented the algorithm on a Sun 4/280 workstation and a Connection Machine. The sequential implementation performs better than the optimal algorithm for large datasets. The parallel implementation on a Connection Machine CM-2 with 32K processors also shows good results.
BibTeX
@article{kf-apcus-92,
author = "Kankanhalli, Mohan and Franklin, Wm Randolph",
title = "Area and Perimeter Computation of the Union of a Set of Iso-Rectangles in Parallel",
year = "1995",
pages = "107--117",
volume = "27",
number = "2",
doi = "https://doi.org/10.1006/jpdc.1995.1076",
month = "June",
journal = "J. Parallel Distrib. Comput.",
keywords = "intersection, parallel computation, grids, area",
href = "\bibhref{85-jpdc95-parallel-union-area}",
mykey = "topology kankanhalli parallel"
}
1994
- Wm Randolph Franklin, Venkateshkumar Sivaswami, David Sun, Mohan Kankanhalli, and Chandrasekhar Narayanaswami.
Calculating the area of overlaid polygons without constructing the overlay.
Cartography and Geographic Information Systems, pages 81–89, April 1994.
[details] [full text]
BibTeX
@article{fsskn-ofmop-93,
author = "Franklin, Wm Randolph and Sivaswami, Venkateshkumar and Sun, David and Kankanhalli, Mohan and Narayanaswami, Chandrasekhar",
title = "Calculating the Area of Overlaid Polygons Without Constructing the Overlay",
year = "1994",
month = "April",
pages = "81--89",
journal = "Cartography and Geographic Information Systems",
succeeds = "f-cmopa-90",
mykey = "overlay kankanhalli chandra",
keywords = "intersection, grids, area",
href = "\bibhref{81-cagis94-overlay}"
}
1993
- Wm Randolph Franklin and Mohan S. Kankanhalli.
Volumes from overlaying 3-D triangulations in parallel.
In D. Abel and B.C. Ooi, editors, Advances in Spatial Databases: Third Intl. Symp., SSD'93, volume 692 of Lecture Notes in Computer Science, pages 477–489.
Springer-Verlag, June 1993.
[details] [full text]
BibTeX
@incollection{fk-vo3tp-93,
author = "Franklin, Wm Randolph and Kankanhalli, Mohan S.",
editor = "Abel, D. and Ooi, B.C.",
title = "Volumes From Overlaying 3-{D} Triangulations in Parallel",
booktitle = "Advances in Spatial Databases: Third Intl. Symp., SSD'93",
publisher = "Springer-Verlag",
month = "June",
year = "1993",
series = "Lecture Notes in Computer Science",
volume = "692",
pages = "477--489",
comment = "SSD = Symp on Large Spatial DBs, Singapore",
href = "\bibhref{78-ssd93-tet}",
keywords = "parallel computation, intersection, volume, CAD",
mykey = "kankanhalli overlay parallel"
}
1990
- Wm Randolph Franklin, Narayanaswami Chandrasekhar, Mohan Kankanhalli, Varol Akman, and Peter YF Wu.
Efficient geometric operations for CAD.
In Michael J. Wozny, Joshua U. Turner, and K. Preiss, editors, Geometric Modeling for Product Engineering, pages 485–498.
Elsevier Science Publishers B.V. (North-Holland), 1990.
[details] [full text]
BibTeX
@incollection{fckaw-egoc-90,
author = "Franklin, Wm Randolph and Chandrasekhar, Narayanaswami and Kankanhalli, Mohan and Akman, Varol and Wu, Peter YF",
editor = "Wozny, Michael J. and Turner, Joshua U. and Preiss, K.",
title = "Efficient Geometric Operations for {CAD}",
booktitle = "Geometric Modeling for Product Engineering",
publisher = "Elsevier Science Publishers B.V. (North-Holland)",
year = "1990",
note = "Selected and expanded papers from the IFIP WG 5.2/NSF Working Conference on Geometric Modeling, Rensselaerville, USA, 18-22 September 1988",
pages = "485--498",
href = "\bibhref{58-wozny90-efficient}",
mykey = "topology chandra akman kankanhalli",
keywords = "intersection, CAD, grids"
}
- Wm Randolph Franklin and Mohan Kankanhalli.
Parallel object-space hidden surface removal.
In Proceedings of SIGGRAPH'90, volume 24, 87–94. August 1990.
[details] [full text]
BibTeX
@inproceedings{fk-poshs-90-in-geom,
author = "Franklin, Wm Randolph and Kankanhalli, Mohan",
title = "Parallel Object-Space Hidden Surface Removal",
booktitle = "Proceedings of SIGGRAPH'90",
journal = "Comput. Graph.",
comments = "Dallas, Texas",
volume = "24",
month = "August",
year = "1990",
pages = "87--94",
href = "\bibhref{62-siggraph90-parallel}",
mykey = "vis3dobj kankanhalli",
keywords = "computer graphics, parallel computation, hidden line/surface elimination, grids"
}
- Mohan Kankanhalli.
Techniques for Parallel Geometric Computations.
PhD thesis, Electrical, Computer, and Systems Engineering Dept., Rensselaer Polytechnic Institute, October 1990.
[details]
BibTeX
@phdthesis{mohan-phd,
Author = "Kankanhalli, Mohan",
Title = "Techniques for Parallel Geometric Computations",
School = "Electrical, Computer, and Systems Engineering Dept., Rensselaer Polytechnic Institute",
Year = "1990",
Month = "October",
mykey = "theses kankanhalli",
Wrfnote = "WRF has"
}
1989
- W. Randolph Franklin, Narayanaswami Chandrasekhar, and Mohan Kankanhalli.
Parallel algorithms for geometric computing.
In Final Program, SIAM Conference on Geometric Design, A17. 6–10 Nov 1989.
(abstract only).
[details]
BibTeX
@inproceedings{fck-pagc-siam-89,
author = "Franklin, W. Randolph and Chandrasekhar, Narayanaswami and Kankanhalli, Mohan",
title = "Parallel Algorithms for Geometric Computing",
pages = "A17",
booktitle = "Final Program, {SIAM} Conference on Geometric Design",
year = "1989",
month = "6--10 Nov",
mykey = "chandra kankanhalli",
note = "(abstract only)"
}
- Wm Randolph Franklin, Mohan Kankanhalli, Chandrasekhar Narayanaswami, and Varol Akman.
Efficient intersection calculations in large databases.
In International Cartographic Association 14th World Conference, A–62 – A–63. Budapest, August 1989.
[details] [full text]
BibTeX
@inproceedings{f-eiclb-89,
author = "Franklin, Wm Randolph and Kankanhalli, Mohan and Narayanaswami, Chandrasekhar and Akman, Varol",
title = "Efficient Intersection Calculations in Large Databases",
booktitle = "International Cartographic Association 14th World Conference",
address = "Budapest",
month = "August",
year = "1989",
pages = "A-62 -- A-63",
href = "\bibhref{60-budapest89-efficient}",
mykey = "akman chandra kankanhalli",
keywords = "intersection, grids"
}
- Wm Randolph Franklin, Mohan Kankanhalli, and Chandrasekhar Narayanaswami.
Efficient primitive geometric operations on large databases.
In Proceedings National Conference Challenge for the 1990s GIS Geographic Information Systems, 1247–1256. Ottawa, 27 February - 3 Mar 1989. Canadian Institute of Surveying and Mapping.
[details] [full text]
BibTeX
@inproceedings{fkn-epgol-89,
author = "Franklin, Wm Randolph and Kankanhalli, Mohan and Narayanaswami, Chandrasekhar",
title = "Efficient Primitive Geometric Operations on Large Databases",
booktitle = "Proceedings National Conference Challenge for the 1990s {GIS} Geographic Information Systems",
address = "Ottawa",
organization = "Canadian Institute of Surveying and Mapping",
month = "27 February - 3 Mar",
year = "1989",
pages = "1247--1256",
mykey = "geometry kankanhalli chandra",
href = "\bibhref{59-ottawa89-efficient}",
keywords = "intersection, CAD, grids"
}
- Varol Akman, Wm Randolph Franklin, Mohan Kankanhalli, and Chandrasekhar Narayanaswami.
Geometric computing and the uniform grid data technique.
Computer Aided Design, 21(7):410–420, 1989.
[details] [full text]
BibTeX
@article{afkn-gcugd-89,
author = "Akman, Varol and Franklin, Wm Randolph and Kankanhalli, Mohan and Narayanaswami, Chandrasekhar",
title = "Geometric Computing and the Uniform Grid Data Technique",
journal = "Computer Aided Design",
year = "1989",
volume = "21",
number = "7",
pages = "410--420",
href = "\bibhref{54-cad89-ug}",
mykey = "akman chandra kankanhalli",
keywords = "intersection, CAD, grids"
}
- Wm Randolph Franklin, Chandrasekhar Narayanaswami, Mohan Kankanhalli, David Sun, Meng-Chu Zhou, and Peter YF Wu.
Uniform grids: a technique for intersection detection on serial and parallel machines.
In Proceedings of Auto Carto 9: Ninth International Symposium on Computer-Assisted Cartography, 100–109. Baltimore, Maryland, 2-7 April 1989.
[details] [full text]
BibTeX
@inproceedings{fnkszw-ugtid-89,
author = "Franklin, Wm Randolph and Narayanaswami, Chandrasekhar and Kankanhalli, Mohan and Sun, David and Zhou, Meng-Chu and Wu, Peter YF",
title = "Uniform Grids: A Technique for Intersection Detection on Serial and Parallel Machines",
booktitle = "Proceedings of Auto Carto 9: Ninth International Symposium on Computer-Assisted Cartography",
year = "1989",
month = "2-7 April",
address = "Baltimore, Maryland",
pages = "100--109",
href = "\bibhref{57-autocarto89-ug}",
mykey = "chandra kankanhalli",
keywords = "parallel computation, intersection, CAD, grids"
}
1988
- Wm Randolph Franklin, Narayanaswami Chandrasekhar., Mohan Kankanhalli, Manoj Seshan, and Varol Akman.
Efficiency of uniform grids for intersection detection on serial and parallel machines.
In Nadia Magnenat-Thalmann and D. Thalmann, editors, New Trends in Computer Graphics (Proc. Computer Graphics International'88), pages 288–297.
Springer-Verlag, 1988.
[details] [full text]
BibTeX
@incollection{fcksa-eugid-88,
author = "Franklin, Wm Randolph and Chandrasekhar., Narayanaswami and Kankanhalli, Mohan and Seshan, Manoj and Akman, Varol",
editor = "Magnenat-Thalmann, Nadia and Thalmann, D.",
title = "Efficiency of uniform grids for intersection detection on serial and parallel machines",
booktitle = "New Trends in Computer Graphics (Proc. Computer Graphics International'88)",
publisher = "Springer-Verlag",
year = "1988",
pages = "288--297",
href = "\bibhref{50-gi88-ug}",
mykey = "akman chandra kankanhalli",
keywords = "parallel computation, intersection, grids"
}
- WR Franklin, N. Chandrasekhar, M. Kankanhalli, and V. Akman.
Fast intersection detection on serial and parallel machines using the uniform grid technique.
1988.
[details] [full text]
BibTeX
@unpublished{fcka-fidspm-88,
author = "Franklin, WR and Chandrasekhar, N. and Kankanhalli, M. and Akman, V.",
title = "Fast intersection detection on serial and parallel machines using the uniform grid technique",
year = "1988",
note = "",
href = "\bibhref{53-unpub88-fast}",
mykey = "akman kankanhalli chandra"
}
- Mohan Kankanhalli.
The uniform grid technique for fast line intersection on parallel machines.
Master's thesis, Electrical,Computer, and Systems Eng. Dept., Rensselaer Polytechnic Institute, April 1988.
[details]
BibTeX
@mastersthesis{mohan-ms,
Author = "Kankanhalli, Mohan",
Title = "The Uniform Grid Technique for Fast Line Intersection on Parallel Machines",
School = "Electrical,Computer, and Systems Eng. Dept., Rensselaer Polytechnic Institute",
Month = "April",
Year = "1988",
mykey = "kankanhalli"
}
No publications match your search. Try another word or clear the search.