More Web Proxy on the site http://driver.im/

Article

Free access

The excell method for efficient geometric access to data

Authors:

Markku Tamminen,

Reijo SulonenAuthors Info & Claims

DAC '82: Proceedings of the 19th Design Automation Conference

Pages 345 - 351

Published: 01 January 1982 Publication History

Abstract

The extendible cell (EXCELL) method provides a data structure for efficient geometric access. It stores geometric data into computer storage blocks corresponding to disjoint variable sized rectangular cells accessible by an address calculation type directory. We describe the method for point files and files of more complicated figures analyzing performance. We report algorithms for the nearest neighbour and point-in-polygon-network problems and describe applications to geographical data bases, hidden line elimination and geometric modeling.

References

[1]

J.L. Bentley and J.H. Friedman, A survey of algorithms and data structures for range searching, ACM Comp. Surv., Vol 11, No 4, 1979

Digital Library

[2]

J.L. Bentley and Th. Ottman, Algorithms for reporting and counting geometric intersections, Report CMU-CS-78-135, Dept. of Comp. Sci., Carnegie-Mellon University, 1978

[3]

J.L. Bentley and D.F Stanat, Analysis of range searches in quad trees, Info. Proc. Lett., 3(1975)6

[4]

J.L. Bentley, B.W. Weide and A.C. Yao, Optimal expected-time algorithms for closest point problems, ACM TOMS, vol 6, no 4, 1980

Digital Library

[5]

J.W. Boyse, Interference detection among solids and surfaces, CACM 22(1979)1

Digital Library

[6]

R. Fagin, J. Nievergelt, N. Pippenger and H.R. Strong, Extendible Hashing - a fast access method for dynamic files, ACM TODS, 3, 1979

Digital Library

[7]

W.R. Franklin, A linear exact hidden surface algorithm, ACM Computer Graphics, Vol 14, No 3,1980

Digital Library

[8]

J.H. Friedman, J.L. Bentley and A. Finkel, An algorithm for finding best matches in logarithmic expected time, ACM TOMS, 6(1977)4

Digital Library

[9]

J.G. Griffiths, Eliminating hidden edges in line drawings, Comput. Aided Des., 11(1979)2

[10]

Proceedings of the Advanced Study Symposium on Topological Data Structures and Geographical Information Systems, Harvard University, 1977

[11]

G.M. Hunter and G. Steiglitz, Operations on images using quadtrees, IEEE PAMI-1, 1979

[12]

D.E. Knuth, The art of computer programming, vol 3: sorting and searching, Addison-Wesley, Reading, Mass., 1973

Digital Library

[13]

M. Mantyla, Methodological background of the Geometric Workbench, Report-HTKK-TKO-B30, Helsinki University of Technology, Espoo, 198l

[14]

R.E. Miles A survey of geometrical probability in the plane, Computer Graphics and Image Processing, 12, 1980

[15]

F.P. Preparata, a new approach to planar point location, SIAM J. Comput., Vol 10, No 3, 1981

Digital Library

[16]

S.D. Roth, Ray casting for modeling solids, Computer Graphics and Image Processing 18(1982)2

[17]

M.I. Shamos, Computational Geometry, PhD thesis, Yale University, 1978

Digital Library

[18]

I.E. Sutherland, R.F. Sproull and R.A. Schumacher, A characterization of ten hidden-surface algorithms, ACM Comp. Surv., Vol 6, No 1, 1974

Digital Library

[19]

M. Tamminen, Helsinki University of Technology, Espoo, Report-HTKK-TKK:

[20]

A20, The extendible cell method for fast geometric access

[21]

B29, Order preserving extendible hashing and bucket tries (to appear in BIT)

[22]

B27, Efficient spatial access to a data base

[23]

B28, Expected performance of some cell based file organization schemes

[24]

B34, Hidden lines using the EXCELL method

[25]

B35, The extendible cell method for closest point problems (to appear in BIT)

[26]

A23, Management of spatially referenced data

[27]

R.B. Tilove, Set membership classification: a unified approach to geometric intersection problems, IEEE trans. Computers, Vol C-29, No 10, 1980

[28]

J.E. Warnock, a hidden surface algorithm for computer generated halftone pictures, Computer Science department, University of Utah, 1969

[29]

M. Wittram, Hidden-line algorithm for scenes of high complexity, Comp. Aided Des., 13(1981)4

Cited By

Blankenagel GGüting R(1994)External segment treesAlgorithmica10.1007/BF0118871712:6(498-532)Online publication date: 1-Dec-1994
https://dl.acm.org/doi/10.1007/BF01188717
Günther OBilmes J(1991)Tree-Based Access Methods for Spatial DatabasesIEEE Transactions on Knowledge and Data Engineering10.1109/69.910643:3(342-356)Online publication date: 1-Sep-1991
https://dl.acm.org/doi/10.1109/69.91064
Orenstein J(1990)A comparison of spatial query processing techniques for native and parameter spacesACM SIGMOD Record10.1145/93605.9874319:2(343-352)Online publication date: 1-May-1990
https://dl.acm.org/doi/10.1145/93605.98743
Show More Cited By

Recommendations

A geometric method for computation of geodesic on parametric surfaces

This paper proposes a geometric algorithm for computation of geodesic on surfaces. The geodesics on surfaces are traced in a simple way which is independent of the complex description of the geodesic equations. Through derivation process, the ...
General surface geometric structures and their applications
An Access Method for Integrating Multi-scale Geometric Data
ADBIS '02: Proceedings of the 6th East European Conference on Advances in Databases and Information Systems

In this paper, an efficient access method for integrating multi-scale geometric data is proposed. Previous access methods do not access multi-scale geometric data efficiently. To solve it, a few access methods for multi-scale geometric data, are known. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DAC '82: Proceedings of the 19th Design Automation Conference

January 1982

919 pages

ISBN:0897910206

Publisher

IEEE Press

Publication History

Published: 01 January 1982

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
321
Total Downloads

Downloads (Last 12 months)32
Downloads (Last 6 weeks)13

Reflects downloads up to 13 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Blankenagel GGüting R(1994)External segment treesAlgorithmica10.1007/BF0118871712:6(498-532)Online publication date: 1-Dec-1994
https://dl.acm.org/doi/10.1007/BF01188717
Günther OBilmes J(1991)Tree-Based Access Methods for Spatial DatabasesIEEE Transactions on Knowledge and Data Engineering10.1109/69.910643:3(342-356)Online publication date: 1-Sep-1991
https://dl.acm.org/doi/10.1109/69.91064
Orenstein J(1990)A comparison of spatial query processing techniques for native and parameter spacesACM SIGMOD Record10.1145/93605.9874319:2(343-352)Online publication date: 1-May-1990
https://dl.acm.org/doi/10.1145/93605.98743
Orenstein JGarcia-Molina H(1990)A comparison of spatial query processing techniques for native and parameter spacesProceedings of the 1990 ACM SIGMOD international conference on Management of data10.1145/93597.98743(343-352)Online publication date: 1-May-1990
https://dl.acm.org/doi/10.1145/93597.98743
Orenstein J(1989)Redundancy in spatial databasesProceedings of the 1989 ACM SIGMOD international conference on Management of data10.1145/67544.66954(295-305)Online publication date: 1-Jun-1989
https://dl.acm.org/doi/10.1145/67544.66954
Orenstein J(1989)Redundancy in spatial databasesACM SIGMOD Record10.1145/66926.6695418:2(295-305)Online publication date: 1-Jun-1989
https://dl.acm.org/doi/10.1145/66926.66954
Seeger BKriegel H(1988)Techniques for Design and Implementation of Efficient Spatial Access MethodsProceedings of the 14th International Conference on Very Large Data Bases10.5555/645915.758354(360-371)Online publication date: 29-Aug-1988
https://dl.acm.org/doi/10.5555/645915.758354
Skyttä JTakala T(1988)A distributed data model for raytracingProceedings of the Third Eurographics conference on Advances in Computer Graphics Hardware10.5555/2421179.2421182(19-26)Online publication date: 11-Sep-1988
https://dl.acm.org/doi/10.5555/2421179.2421182
Skyttä JTakala T(1987)Partially ordered search indices in the organizationof a fixed hierarchyProceedings of the Second Eurographics conference on Advances in Computer Graphics Hardware10.5555/2421159.2421163(39-46)Online publication date: 24-Aug-1987
https://dl.acm.org/doi/10.5555/2421159.2421163
Skyttä JTakala T(1986)Utilization of VLSI for creating an active data base of 3-D geometric modelsProceedings of the First Eurographics conference on Advances in Computer Graphics Hardware10.5555/2421143.2421154(83-93)Online publication date: 1-Aug-1986
https://dl.acm.org/doi/10.5555/2421143.2421154
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents