The DOI matches its Crossref record.
Computational Geometry--An Introduction.
Abstract
From the reviews: This book offers a coherent treatment, at the graduate textbook level, of the field that has come to be known in the last decade or so as computational geometry...The book is well organized and lucidly written; a timely contribution by two founders of the field. It clearly demonstrates that computational geometry in the plane is now a fairly well-understood branch of computer science and mathematics. It also points the way to the solution of the more challenging problems in dimensions higher than two.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cited by
Cortical Surface-Based Analysis
Dale, A. M., Fischl, B., & Sereno, M. I. (1999) · NeuroImage · doi:10.1006/nimg.1998.0395 · Cited by 10,910
An efficient k-means clustering algorithm: analysis and implementation
Kanungo, T., Mount, D. M., Netanyahu, N. S., Piatko, C. D., Silverman, R., & Wu, A. Y. (2002) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2002.1017616 · Cited by 5,660
LOF: identifying density-based local outliers
Breunig, M. M., Kriegel, H.-P., Ng, R. T., & Sander, J. (2000) · ACM SIGMOD Record · doi:10.1145/335191.335388 · Cited by 5,207
Voronoi diagrams—a survey of a fundamental geometric data structure
Aurenhammer, F. (1991) · ACM Computing Surveys · doi:10.1145/116873.116880 · Cited by 4,340
LOF: identifying density-based local outliers
Breunig, M. M., Kriegel, H.-P., Ng, R. T., & Sander, J. (2000) · Proceedings of the 2000 ACM SIGMOD international conference on Management of data · doi:10.1145/342009.335388 · Cited by 4,149
Three-dimensional alpha shapes
Edelsbrunner, H., & Mücke, E. P. (1994) · ACM Transactions on Graphics · doi:10.1145/174462.156635 · Cited by 2,488
Iterative point matching for registration of free-form curves and surfaces
Zhang, Z. (1994) · International Journal of Computer Vision · doi:10.1007/bf01427149 · Cited by 2,402
An optimal algorithm for approximate nearest neighbor searching fixed dimensions
Arya, S., Mount, D. M., Netanyahu, N. S., Silverman, R., & Wu, A. Y. (1998) · Journal of the ACM · doi:10.1145/293347.293348 · Cited by 2,300
Centroidal Voronoi Tessellations: Applications and Algorithms
Du, Q., Faber, V., & Gunzburger, M. (1999) · SIAM Review · doi:10.1137/s0036144599352836 · Cited by 2,244
Efficient algorithms for mining outliers from large data sets
Ramaswamy, S., Rastogi, R., & Shim, K. (2000) · ACM SIGMOD Record · doi:10.1145/335191.335437 · Cited by 1,860
Fischl, B., Liu, A., & Dale, A. M. (2001) · IEEE Transactions on Medical Imaging · doi:10.1109/42.906426 · Cited by 1,751
A TRAIT-BASED TEST FOR HABITAT FILTERING: CONVEX HULL VOLUME
Cornwell, W. K., Schwilk, D. W., & Ackerly, D. D. (2006) · Ecology · doi:10.1890/0012-9658(2006)87[1465:attfhf]2.0.co;2 · Cited by 1,294
Coverage for robotics – A survey of recent results
Choset, H. (2001) · Annals of Mathematics and Artificial Intelligence · doi:10.1023/a:1016639210559 · Cited by 1,209
Distance-based outliers: algorithms and applications
Knorr, E. M., Ng, R. T., & Tucakov, V. (2000) · The VLDB Journal The International Journal on Very Large Data Bases · doi:10.1007/s007780050006 · Cited by 1,195
A sweepline algorithm for Voronoi diagrams
Fortune, S. (1987) · Algorithmica · doi:10.1007/bf01840357 · Cited by 1,134
Some new indexes of cluster validity
Bezdek, J. C., & Pal, N. R. (1998) · IEEE Transactions on Systems, Man and Cybernetics, Part B (Cybernetics) · doi:10.1109/3477.678624 · Cited by 1,132
Fraczkiewicz, R., & Braun, W. (1998) · Journal of Computational Chemistry · doi:10.1002/(sici)1096-987x(199802)19:3<319::aid-jcc6>3.0.co;2-w · Cited by 1,120
Eisenhaber, F., Lijnzaad, P., Argos, P., Sander, C., & Scharf, M. (1995) · Journal of Computational Chemistry · doi:10.1002/jcc.540160303 · Cited by 1,055
Core Vector Machines: Fast SVM Training on Very Large Data Sets
Tsang, I. W.-H., Kwok, J. T.-Y., & Cheung, P.-M. (2005) · doi:10.5555/1046920.1058114 · Cited by 928
Maurer, C. R., Qi, R., & Raghavan, V. (2003) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2003.1177156 · Cited by 911
Topology representing networks
Martinetz, T., & Schulten, K. (1994) · Neural Networks · doi:10.1016/0893-6080(94)90109-0 · Cited by 883
When Gaussian Process Meets Big Data: A Review of Scalable GPs
Liu, H., Ong, Y.-S., Shen, X., & Cai, J. (2020) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2019.2957109 · Cited by 878
Efficient collision detection using bounding volume hierarchies of k-DOPs
Klosowski, J. T., Held, M., Mitchell, J. S. B., Sowizral, H., & Zikan, K. (1998) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/2945.675649 · Cited by 873
Gross motion planning—a survey
Hwang, Y. K., & Ahuja, N. (1992) · ACM Computing Surveys · doi:10.1145/136035.136037 · Cited by 826
A weighted nearest neighbor algorithm for learning with symbolic features
Cost, S., & Salzberg, S. (1993) · Machine Learning · doi:10.1007/bf00993481 · Cited by 764
Turk, G. (1992) · Proceedings of the 19th annual conference on Computer graphics and interactive techniques · doi:10.1145/133994.134008 · Cited by 738
An introduction to spatial database systems
G�ting, R. H. (1994) · The VLDB Journal · doi:10.1007/bf01231602 · Cited by 724
Outline for a theory of intelligence
Albus, J. S. (1991) · IEEE Transactions on Systems, Man, and Cybernetics · doi:10.1109/21.97471 · Cited by 722
Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
Edelsbrunner, H., & Mücke, E. P. (1990) · ACM Transactions on Graphics · doi:10.1145/77635.77639 · Cited by 711
QSAR Applicability Domain Estimation by Projection of the Training Set in Descriptor Space: A Review
Jaworska, J., Nikolova-Jeliazkova, N., & Aldenberg, T. (2005) · Alternatives to Laboratory Animals · doi:10.1177/026119290503300508 · Cited by 682
Relative neighborhood graphs and their relatives
Jaromczyk, J. W., & Toussaint, G. T. (1992) · Proceedings of the IEEE · doi:10.1109/5.163414 · Cited by 664
Algorithms for packet classification
Gupta, P., & McKeown, N. (2001) · IEEE Network · doi:10.1109/65.912717 · Cited by 655
Scattered data interpolation methods for electronic imaging systems: a survey
Amidror, I. (2002) · Journal of Electronic Imaging · doi:10.1117/1.1455013 · Cited by 637
Minutia Cylinder-Code: A New Representation and Matching Technique for Fingerprint Recognition
Cappelli, R., Ferrara, M., & Maltoni, D. (2010) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2010.52 · Cited by 637
Exploratory Data Mining and Data Cleaning
Dasu, T., & Johnson, T. (2003) · Wiley Series in Probability and Statistics · doi:10.1002/0471448354 · Cited by 618
The image foresting transform: theory, algorithms, and applications
Falcao, A. X., Stolfi, J., & de Alencar Lotufo, R. (2004) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2004.1261076 · Cited by 614
ICP registration using invariant features
Sharp, G. C., Lee, S. W., & Wehe, D. K. (2002) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.982886 · Cited by 614
Blanche-an experiment in guidance and navigation of an autonomous robot vehicle
Cox, I. J. (1991) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.75902 · Cited by 588
Proceedings of the Michigan Morphometrics Workshop.
Warheit, K. I., Rohlf, F. J., & Bookstein, F. L. (1992) · Systematic Biology · doi:10.2307/2992576 · Cited by 557
Generation of 3D representative volume elements for heterogeneous materials: A review
Bargmann, S., Klusemann, B., Markmann, J., Schnabel, J. E., Schneider, K., Soyarslan, C., & Wilmers, J. (2018) · Progress in Materials Science · doi:10.1016/j.pmatsci.2018.02.003 · Cited by 546
Pad: an alternative approach to the computer interface
Perlin, K., & Fox, D. (1993) · Proceedings of the 20th annual conference on Computer graphics and interactive techniques · doi:10.1145/166117.166125 · Cited by 543
Vempala, S. (2005) · DIMACS Series in Discrete Mathematics and Theoretical Computer Science · doi:10.1090/dimacs/065 · Cited by 538
A Measurement Theory for Time Geography
Miller, H. J. (2005) · Geographical Analysis · doi:10.1111/j.1538-4632.2005.00575.x · Cited by 532
Coverage in wireless ad hoc sensor networks
Li, X.-Y., Wan, P.-J., & Frieder, O. (2003) · IEEE Transactions on Computers · doi:10.1109/tc.2003.1204831 · Cited by 521
The Bernstein polynomial basis: A centennial retrospective
Farouki, R. T. (2012) · Computer Aided Geometric Design · doi:10.1016/j.cagd.2012.03.001 · Cited by 506
Designer disordered materials with large, complete photonic band gaps
Florescu, M., Torquato, S., & Steinhardt, P. J. (2009) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0907744106 · Cited by 503
Approximating polyhedra with spheres for time-critical collision detection
Hubbard, P. M. (1996) · ACM Transactions on Graphics · doi:10.1145/231731.231732 · Cited by 491
Randomized incremental construction of Delaunay and Voronoi diagrams
Guibas, L. J., Knuth, D. E., & Sharir, M. (1992) · Algorithmica · doi:10.1007/bf01758770 · Cited by 479
Discovery of spatial association rules in geographic information databases
Koperski, K., & Han, J. (1995) · Lecture Notes in Computer Science · doi:10.1007/3-540-60159-7_4 · Cited by 452
Optimal multi-step k-nearest neighbor search
Seidl, T., & Kriegel, H.-P. (1998) · Proceedings of the 1998 ACM SIGMOD international conference on Management of data · doi:10.1145/276304.276319 · Cited by 442
Almost optimal set covers in finite VC-dimension
Brönnimann, H., & Goodrich, M. T. (1995) · Discrete & Computational Geometry · doi:10.1007/bf02570718 · Cited by 441
Orienting polygonal parts without sensors
Goldberg, K. Y. (1993) · Algorithmica · doi:10.1007/bf01891840 · Cited by 437
Geometric Shortest Paths and Network Optimization
Mitchell, J. S. B. (2000) · Handbook of Computational Geometry · doi:10.1016/b978-044482537-7/50016-4 · Cited by 427
Dynamic social network analysis using latent space models
Sarkar, P., & Moore, A. W. (2005) · ACM SIGKDD Explorations Newsletter · doi:10.1145/1117454.1117459 · Cited by 422
The Knowledge-Gradient Policy for Correlated Normal Beliefs
Frazier, P., Powell, W., & Dayanik, S. (2009) · INFORMS Journal on Computing · doi:10.1287/ijoc.1080.0314 · Cited by 408
MODIS land data storage, gridding, and compositing methodology: Level 2 grid
Wolfe, R. E., Roy, D. P., & Vermote, E. (1998) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/36.701082 · Cited by 397
Voronoi Diagrams**Partially supported by the Deutsche Forschungsgemeinschaft, grant K1 655 2-2.
Aurenhammer, F., & Klein, R. (2000) · Handbook of Computational Geometry · doi:10.1016/b978-044482537-7/50006-1 · Cited by 392
Efficient distance computation between non-convex objects
Quinlan, S. (2002) · Proceedings of the 1994 IEEE International Conference on Robotics and Automation · doi:10.1109/robot.1994.351059 · Cited by 391
Incremental Local Outlier Detection for Data Streams
Pokrajac, D., Lazarevic, A., & Latecki, L. J. (2007) · 2007 IEEE Symposium on Computational Intelligence and Data Mining · doi:10.1109/cidm.2007.368917 · Cited by 386
Processing images and video for an impressionist effect
Litwinowicz, P. (1997) · Proceedings of the 24th annual conference on Computer graphics and interactive techniques - SIGGRAPH '97 · doi:10.1145/258734.258893 · Cited by 384
Hierarchical face clustering on polygonal surfaces
Garland, M., Willmott, A., & Heckbert, P. S. (2001) · Proceedings of the 2001 symposium on Interactive 3D graphics · doi:10.1145/364338.364345 · Cited by 375
Outlier mining in large high-dimensional data sets
Angiulli, F., & Pizzuti, C. (2005) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2005.31 · Cited by 365
Fully automatic registration of multiple 3D data sets
Huber, D. F., & Hebert, M. (2003) · Image and Vision Computing · doi:10.1016/s0262-8856(03)00060-x · Cited by 356
Classes of graphs which approximate the complete euclidean graph
Keil, J. M., & Gutwin, C. A. (1992) · Discrete & Computational Geometry · doi:10.1007/bf02187821 · Cited by 354
A review of statistical data association techniques for motion correspondence
Cox, I. J. (1993) · International Journal of Computer Vision · doi:10.1007/bf01440847 · Cited by 346
Analytical shape computation of macromolecules: I. molecular area and volume through alpha shape
Liang, J., Edelsbrunner, H., Fu, P., Sudhakar, P. V., & Subramaniam, S. (1998) · Proteins: Structure, Function, and Genetics · doi:10.1002/(sici)1097-0134(19981001)33:1<1::aid-prot1>3.0.co;2-o · Cited by 319
New applications of random sampling in computational geometry
Clarkson, K. L. (1987) · Discrete & Computational Geometry · doi:10.1007/bf02187879 · Cited by 317
Terrestrial Laser Scanning-Based Structural Damage Assessment
Olsen, M. J., Kuester, F., Chang, B. J., & Hutchinson, T. C. (2010) · Journal of Computing in Civil Engineering · doi:10.1061/(asce)cp.1943-5487.0000028 · Cited by 311
A simple algorithm for nearest neighbor search in high dimensions
Nene, S. A., & Nayar, S. K. (1997) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.615448 · Cited by 311
Incremental topological flipping works for regular triangulations
Edelsbrunner, H., & Shah, N. R. (1996) · Algorithmica · doi:10.1007/bf01975867 · Cited by 303
Automatic reconstruction of surfaces and scalar fields from 3D scans
Bajaj, C. L., Bernardini, F., & Xu, G. (1995) · Proceedings of the 22nd annual conference on Computer graphics and interactive techniques - SIGGRAPH '95 · doi:10.1145/218380.218424 · Cited by 292
Mavriplis, D. J. (1997) · Annual Review of Fluid Mechanics · doi:10.1146/annurev.fluid.29.1.473 · Cited by 292
A Random Sampling Scheme for Path Planning
Barraquand, J., Kavraki, L., Latombe, J.-C., Motwani, R., Li, T.-Y., & Raghavan, P. (1997) · The International Journal of Robotics Research · doi:10.1177/027836499701600604 · Cited by 277
Liang, J., & Dill, K. A. (2001) · Biophysical Journal · doi:10.1016/s0006-3495(01)75739-6 · Cited by 273
Outlier Detection with Kernel Density Functions
Latecki, L. J., Lazarevic, A., & Pokrajac, D. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-73499-4_6 · Cited by 273
Geometric spanner for routing in mobile networks
Gao, J., Guibas, L. J., Hershberger, J. E., Zhang, L., & Zhu, A. (2001) · ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc) · doi:10.1145/501422.501424 · Cited by 261
Computational Capabilities of Graph Neural Networks
Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., & Monfardini, G. (2009) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2008.2005141 · Cited by 225
Lee, J. K., Lee, J.-M., Kim, J. S., Kim, I. Y., Evans, A. C., & Kim, S. I. (2006) · NeuroImage · doi:10.1016/j.neuroimage.2005.12.044 · Cited by 108
Smith, Z., Strobel, M., Vani, B. P., & Tiwary, P. (2024) · Journal of Chemical Information and Modeling · doi:10.1021/acs.jcim.3c01698 · Cited by 47
Close-Point Spatial Tests and Their Application to Random Number Generators
L'Écuyer, P., Cordeau, J.-F., & Simard, R. (2000) · Operations Research · doi:10.1287/opre.48.2.308.12385 · Cited by 38
Metadata
- Authors
- Atallah, M. J., Preparata, F. P., & Shamos, M. I.
- Venue
- Mathematics of Computation
- Publisher
- JSTOR
- Published
- 1986-10
- Volume
- 47
- Issue
- 176
- Pages
- 763
- ISSN
- 0025-5718 (ISSN-L)
- OpenAlex
- W2005314985
- Cited by
- 4,238
- References
- 0
- FWCI
- 51.89
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.