Voronoi diagrams—a survey of a fundamental geometric data structure
Tóm tắt
Từ khóa
Tài liệu tham khảo
AGARWAL P. K., 1990, Proceedings of the 6th Annual ACM Symposium on Computational Geometry, 203
AGGARWAL A., 1987, Proceedings of the 3rd Annual ACM Symposium on Computational Geometry, 278
AGGARWAL A., 1990, Proceedings of the 22nd Annual ACM Symposium on STOC, 331
AGGARWAL A., 1989, Proceedings of the 5th Annual ACM Symposium on Computational Geometry, 283
AKL S., 1983, A note on Euclidean matchings, triangulations, and spanning trees, J. Comb. Inf. Syst. Sci., 8, 169
ALEXANDERSON G. L., 1978, Simple partition of space, Math. Magazine, 51, 220, 10.1080/0025570X.1978.11976715
ALT H., 1990, Algorithmic aspects of motion planning: A tutorial (part 2), Algorithms Rev., 1, 61
AONUMA H., 1990, Proceedings of 6th Annual ACM Symposium on Computational Geometry., 225
ARNOLD D. B., 1984, The use of Voronoi tessellations in processing soil survey results, IEEE Comput. Graph. Appl., 4, 22, 10.1109/MCG.1984.276058
ARONOV B., 1989, On the geodesic Voronoi diagram of point sites in a simple polygon, Algorithmica, 4, 109, 10.1007/BF01553882
ARONOV B., 1988, Proceedings of the 4th Annual ACM Symposium on Computational Geometry., 229, 10.1145/73393.73417
ARONOV B., 1990, Proceedings of the 6th Annual ACM Symposium on Computational Geometry., 112
ASANO T., Perspectives in Computing 15, 51
ASANO T., 1988, Proceedings of the 4th Annual ACM Symposium on Computational Geometry, 252, 10.1145/73393.73419
ASH P. F., 1985, Recognizing Dirichlet tessellations, Geometriae Dedicata, 19, 175
ASH P. F., 1986, Generalized Dirichlet tessellations, Geometrme Dedicata, 20, 209, 10.1007/BF00164401
ASH P. F., 1988, Boston, 231
AUGENBAUM J. M., 1985, On the construction of the Voronoi mesh on a sphere, J. Comput. Phys., 59, 177, 10.1016/0021-9991(85)90140-8
AURENHAMMER F., 1987, A criterion for the affine equivalence of cell complexes in R d and convex polyhedra in Rd+ 1, Discrete Comput. Geometry, 2, 49, 10.1007/BF02187870
AURENHAMMER F., 1988, Linear combinations from power domains, Geometriae Dedicata, 28, 45, 10.1007/BF00147799
AURENHAMMER F., 1984, An optimal algorithm for constructing the weighted Voronoi diagram in the plane, Pattern Recognition, 17, 251, 10.1016/0031-3203(84)90064-5
AURENHAMMER F., 1988, Geometric relations among Voronoi diagrams, Geometriae Dedicata, 27, 65, 10.1007/BF00181613
AURENHAMMER F., Proceedings of the 7th Annual ACM Symposium on Computational Geometry., 142
AURENHAMMER F. AND STOCKL G. 1988. On the peeper's Voronoi diagram. Rep. 264 IIG-TU Graz Austria. AURENHAMMER F. AND STOCKL G. 1988. On the peeper's Voronoi diagram. Rep. 264 IIG-TU Graz Austria.
AURENHAMMER F. ST(SCKL G. AND WELZL E. 1991. The post-office problem for fuzzy point sets. Rep. 91-07 FU Berlin Germany. AURENHAMMER F. ST(SCKL G. AND WELZL E. 1991. The post-office problem for fuzzy point sets. Rep. 91-07 FU Berlin Germany.
AVIS D., 1983, Algorithms for computing d-dimenslonal Voronoi diagrams and their duals, Adv. Comput. Res., 1, 159
BABENKO V. F., 1977, On the optimal cubature ormulae on certain classes of continuous functions, Analys~s Math., 3, 3, 10.1007/BF02333249
BADDELEY A., 1977, A fourth note on recent research in geometrical probability, Adv. Appl. Probab., 9, 824, 10.2307/1426702
BENTLEY J. L., 1979, A note on Euclidean near neighboring searching in the plane, Inf. Process. Lett., 8, 133
BERN M. W. EPPSTEIN D. AND GILBERT J. 1990. Provably good mesh generation. Manuscript XEROX Palo Alto Research Center Palo Alto Calif. BERN M. W. EPPSTEIN D. AND GILBERT J. 1990. Provably good mesh generation. Manuscript XEROX Palo Alto Research Center Palo Alto Calif.
BESAG J., 1974, Spatial interaction and the statistical analysis of lattice systems, J. Roy. Statist. Soc. B, 36, 192, 10.1111/j.2517-6161.1974.tb00999.x
BIEBERBACH L., 1912, l)ber die Bewegungsgruppen der euklidischen Riiume I, II. Math. Ann., 72, 400
BLUM H., 1967, Proceedings of the Symposium on Models for the Perception of Speech and Visual Form. Weiant Whaten- Dunn, Ed. MIT Press, 362
BLUM H., 1973, Biological shape and visual science (Part I), J. Theol'. Biol., 38, 205, 10.1016/0022-5193(73)90175-6
BOISSONNAT J.-D., 1986, Proceedings of 2nd Annual ACM Symposium on Computational Geometry, 260, 10.1145/10515.10543
BOOTS B. N., 1979, Weighting Thiessen polygons, Econ. Geography, 248
CATMOG 45
BRASSEL K. E., 1979, A procedure to generate Thiessen polygons, Geograph. Anal., 11, 289, 10.1111/j.1538-4632.1979.tb00695.x
BR~SSON E., 1989, Proceedings of the 5th Annual ACM Symposium on Computational Geometry., 218
BRONDSTED A. 1983. An Introduction to Convex Polytopes. Springer New York Heidelberg Berlin. BRONDSTED A. 1983. An Introduction to Convex Polytopes. Springer New York Heidelberg Berlin.
BROSTOW W., 1978, Construction of Voronoi polyhedra, J. Comput. Phys., 29, 81, 10.1016/0021-9991(78)90110-9
BROWN K. Q., 1979, Voronoi diagrams from convex hulls, Inf. Process. Lett., 9, 223, 10.1016/0020-0190(79)90074-7
BROWN K. Q. 1980. Geometric transforms for fast geometric algorithms. Ph.D. dissertation Carnegie-Mellon Univ. Pittsburgh Penn. BROWN K. Q. 1980. Geometric transforms for fast geometric algorithms. Ph.D. dissertation Carnegie-Mellon Univ. Pittsburgh Penn.
BRUMBERGER H., 1983, Voronoi cells: An interesting and potentially useful cell model for interpreting the small angle scattering of catalysts, J. Appl. Crystallogr., 16, 83, 10.1107/S002188988300998X
CALABI L., 1968, Shape recognition, prairie fires, convex deficiencies, and skeletons, Am. Math. Monthly, 75, 335, 10.1080/00029890.1968.11970990
CHAZELLE B., 1990, Proceedings of the 6th Annual ACM Symposium on Computational Geometry, 116
CHEW L. P., 1986, Proceedings of the 2nd Annual ACM Symposium on Computational Geometry., 169, 10.1145/10515.10534
HEW L. P. 1989b. Guaranteed-quality triangular meshes. Rep. TR 89-983 Dept. Comput. Sci. Cornell Univ. Ithaca N.Y. HEW L. P. 1989b. Guaranteed-quality triangular meshes. Rep. TR 89-983 Dept. Comput. Sci. Cornell Univ. Ithaca N.Y.
CHEW L. P., 1985, Proceedings of the 1st Annual ACM Symposium on Computational Geometry., 235, 10.1145/323233.323264
CHEW L. P., 1989, Proceedings of the 5th Annual ACM Symposium on Computational Geometry., 167
Chow A. 1980. Parallel algorithms for geometric problems. Ph.D. dissertation. Dept. Comput. Sci. Univ. of Illinois Urbana Ill. Chow A. 1980. Parallel algorithms for geometric problems. Ph.D. dissertation. Dept. Comput. Sci. Univ. of Illinois Urbana Ill.
CI~ISTOFIDES N., 1976, Symposium on Algorithms and Complexity, Carnegie-Mellon Univ., Penn.
CLARKSON K. L., 1987, New applications of random sampling to computational geometry, Discrete Comput. Geom., 2, 195, 10.1007/BF02187879
CLARKSON K. L. 1989. An algorithm for geometric minimum spanning trees requiring nearly linear expected time. Algorithmica4 461-468. CLARKSON K. L. 1989. An algorithm for geometric minimum spanning trees requiring nearly linear expected time. Algorithmica4 461-468.
CLARKSON K. L., 1988, Proceedings of the 4th Annual ACM Symposium on Computational Geometry., 12, 10.1145/73393.73395
COLE R., 1990, Merging free trees in parallel for efficient Voronoi diagram construction, Springer LNCS, 443, 432
CONWAY J. M., 1982, Voronoi regions of lattices, second moments of polytopes, and quantization, IEEE Trans. Inf. Theory IT-28, 211, 10.1109/TIT.1982.1056483
CRAI, 1978, The Monte Carlo generation of random polygons, Comput. Geosci., 4, 131, 10.1016/0098-3004(78)90082-1
CRAPO H., 1979, Structural rigidity, Struct. Topol., 1, 13
CR RIVE, 1979, Distortion of certain Voronoi tessellations when one particle moves, J. Appl. Probab., 16, 95, 10.2307/3213378
DAVID E. E., 1982, Voronoi polyhedra as a tool for studying solvation structure, J. Chem. Phys., 76, 4611, 10.1063/1.443540
DE FLORIANI L. FALCIDIENO B. PIENOVI C. AND NAG~ G. 1988. On sorting triangles in a Delaunay tessellation. Rep. Inst. Mat. Appl. Consiglio Nazionale della Richerche Genova Italy. DE FLORIANI L. FALCIDIENO B. PIENOVI C. AND NAG~ G. 1988. On sorting triangles in a Delaunay tessellation. Rep. Inst. Mat. Appl. Consiglio Nazionale della Richerche Genova Italy.
DEHNE F. AND KLEIN R. 1987. An optimal algorithm for computing the Voronoi diagram on a cone. Rep. SCS-TR-122 School Comput. Sci. Carleton Univ. Ottawa Canada. DEHNE F. AND KLEIN R. 1987. An optimal algorithm for computing the Voronoi diagram on a cone. Rep. SCS-TR-122 School Comput. Sci. Carleton Univ. Ottawa Canada.
DEHNE F., 1985, Proceedings of the 1st Annual ACM Symposium on Computational Geometry., 245, 10.1145/323233.323265
DELAUNAY B. N., 1932, Neue Darstellung der geometrischen Kristallographie, Z. Kristallograph., 84, 109
DELAUNAY B. N., 1934, Sur la sphere vide, Bull. Acad. Science USSR VII: Class. Sci. Math., 793
DELAUNAY B. N., 1963, Theorie der regul~iren Dirichletschen Zerlegungen des n-dimensionalen euklidischen Raumes, Schrifienre~he Int. Math. Dtsch. Akad. Wiss. Berlin, 13, 27
DELAUNAY B. N., 1978, Combinatorial and metric theory of planigons, Trudy Mat. Inst. Steklov, 148, 109
DEWDNEY A. K. 1977. Complexity of nearest neighbour searching in three and higher dimensions. Rep. 28 Univ. of Western Ontario London Ontario. DEWDNEY A. K. 1977. Complexity of nearest neighbour searching in three and higher dimensions. Rep. 28 Univ. of Western Ontario London Ontario.
DEWDNEY A. K., 1977, A convex partition of R3 with applications to Crum's problem and Knuth's post-office problem, Util. Math., 12, 193
DILLENCOURT M. B., 1987, Proceedings of the 3rd Annual ACM Symposium on Computational Geometry., 186
DIRICHLET G. L., 1850, Uber die Reduction der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen. J. Re~ne u, Angew. Math., 40, 209
DOBKIN D. P., 1989, PrimL tives for the manipulation of three-dimensional subdivisions, Algorithmica, 4, 3, 10.1007/BF01553877
DRYSDALE R. L., 1990, Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms., 159
DWYER R. A., 1987, A faster divide-and-conquer algorithm for constructing Delaunay triangulations, Algorithmica, 2, 137, 10.1007/BF01840356
DWYER R. A., 1989, Proceedings of the 5th Annual ACM Symposium on Computational Geometry., 326
EDELSBRUNNER H. 1987. Algorithms in Combinatorial Geometry. Springer Berlin-Heidelberg. EDELSBRUNNER H. 1987. Algorithms in Combinatorial Geometry. Springer Berlin-Heidelberg.
EDELSBRUNNER, 1989, Proceedings of the 5th Annual ACM Symposium on Computational Geometry., 145
EDELSBRUNNER H., 1985, Finding extreme points in three dimensions and solving the post-office problem in the plane, Inf. Process. Lett., 21, 39, 10.1016/0020-0190(85)90107-3
EDELSBRUNNER H., 1985, On the number of line separations of a finite set in the plane, J. Combin. Theory Ser. A, 15, 10.1016/0097-3165(85)90017-2
EDELSBRUNNER H., 1989, The upper envelope of piecewise linear functions: algorithms and applications, Discrete Comput. Geom., 4, 311, 10.1007/BF02187733
EDELSBRUNNER H., 1983, On the shape of a set of points in the plane, IEEE Trans. Inf. Theory IT-29,551-559., 10.1109/TIT.1983.1056714
EDELSBRUNNER H., 1987, Testing the necklace condition for shortest tours and optimal factors in the plane, Springer LNCS, 267, 364
EHRLICH P. E., 1979, Dirichlet regions in manifolds without conjugate points, Comment. Math. Helvet., 54, 642, 10.1007/BF02566298
EISELT H. A., 1986, Voronoi diagrams and their use: A survey. Part I: Theory; Part II: Applications. In S. Goyal, Ed. Proceedings of the ASAC, 7, 2. pp. 98
ENGEL P., 1981, lJber Wirkungsbereichsteilungen mit kubischer Symmetrie, Z. Kristallograph., 154, 199
EPPSTE~N D., 1990, Finding the k smallest spanning trees, Springer LNCS, 447, 38
FAIRFIELD J., 1979, Proceedings of the IEEE Conference on Systems Man Cybernetics., 60
FAIRFIELD J., 1983, Segmenting dot patterns by Voronoi diagram concavity, IEEE Trans. Part. Anal. Mach. Int. PAMI-5, 104, 10.1109/TPAMI.1983.4767353
FEDEROFF E. S., 1885, Elemente der Lehre yon den Figuren, Verh. Russ Min. Ges. St. Petersburg, 21, 1
FIELD D. A., 1986, Proceedings of the 2nd Annual ACM Symposium on Computational Geometry., 246, 10.1145/10515.10542
FINNEY J. L., 1979, Procedure for the construction of Voronoi polyhedra. Note, J. Comput. Phys., 32, 137, 10.1016/0021-9991(79)90146-3
FORTUNE S., 1985, A fast algorithm for polygon containment by translation, Springer LNCS, 194, 189
FORTUNE S., 1987, A sweepline algorithm for Voronoi diagrams, Algorithmica, 2, 153, 10.1007/BF01840357
FORTUNE S. 1988. Sorting helps for Voronoi diagrams. Manuscript ATT Bell Lab. Murray Hill N.J. FORTUNE S. 1988. Sorting helps for Voronoi diagrams. Manuscript ATT Bell Lab. Murray Hill N.J.
FRANK F. C., 1958, Complex alloy structures regarded as sphere packings, Acta Crystallogr., 11, 184, 10.1107/S0365110X58000487
GABRIEL K. R, 1969, A new statistical approach to geographic variation analysis, Syst. Zoology, 18, 259, 10.2307/2412323
GAMBINI R. 1966. A computer program for calculating lines of equilibrium between multiple centers of attraction. Manuscript Center of Regional Studies Univ. of Kansas Lawrence Kan. GAMBINI R. 1966. A computer program for calculating lines of equilibrium between multiple centers of attraction. Manuscript Center of Regional Studies Univ. of Kansas Lawrence Kan.
GAREY M. R., 1976, Proceedings of the 8th Annual ACM Symposium on STOC., 10
GAUSS C. F., 1840, Recursion der 'Untersuchungen fiber die Eigenschaften der positiven tern~iren quadratischen Formen von Ludwig August Seeber, J. Reine Angew. Math., 20, 312
GILBERT E. N., 1962, Random subdivisions of space into crystals, Ann. Math. Star., 33, 958, 10.1214/aoms/1177704464
GOODRICH M. T., 1989, Constructing the Voronoi diagram of a set of line segments in parallel, Springer LNCS, 382, 12
GOWDA I. G., 1983, Dynamic Voronoi diagrams, IEEE Trans. Inf Theory IT-29, 724, 10.1109/TIT.1983.1056738
GREEN P. J., 1977, Computing Dirichlet tesselations in the plane, Comput. J., 21, 168, 10.1093/comjnl/21.2.168
GRUBER P. M. AND LEKKERKERKER C. G. 1988. Geometry of Numbers. North-Holland Publishing Co. Amsterdam. GRUBER P. M. AND LEKKERKERKER C. G. 1988. Geometry of Numbers. North-Holland Publishing Co. Amsterdam.
GRUBER P. M. AND RYSKOV S. S. 1987. Facet-tofacet implies face-tofface. Manuscript. GRUBER P. M. AND RYSKOV S. S. 1987. Facet-tofacet implies face-tofface. Manuscript.
GRfiNBAUM B. 1967. Convex Polytopes. Interscience New York. GRfiNBAUM B. 1967. Convex Polytopes. Interscience New York.
GR BAUM, 1980, Tilings with congruent tiles, Bull. Am. Math. Soc., 3, 951, 10.1090/S0273-0979-1980-14827-2
GRUNBAUM B. AND SHEPHARD G. C. 1987. Tilings and Patterns. Freeman and Co. New York. GRUNBAUM B. AND SHEPHARD G. C. 1987. Tilings and Patterns. Freeman and Co. New York.
GUIBAS L. J., 1990, Randomized incremental construction of Delaunay and Voronoi diagrams, Springer LNCS, 443, 414
GUIBAS L. J. MITCHELL J. S. B. AND ROOS T. 1991. Voronoi diagrams of moving points in the plane. Springer LNCS. In press. GUIBAS L. J. MITCHELL J. S. B. AND ROOS T. 1991. Voronoi diagrams of moving points in the plane. Springer LNCS. In press.
HARTIGAN J. A. 1975. Clustering Algorithms. John Wiley New York. HARTIGAN J. A. 1975. Clustering Algorithms. John Wiley New York.
HLNRICHS K., 1988, A sweep algorithm for the all-nearestneighbors problem, Springer LNCS, 333, 43
HORTON R. E., 1917, Rational study of rainfall data make~ possible bettor estimates of water yield, Eng. News-Record, 211
HOWE S. E. 1978. Estimating regions and clustering spatial data: Analysis and implementation of methods using the Voronoi diagram. Ph.D. dissertation Brown Univ. Providence R.I. HOWE S. E. 1978. Estimating regions and clustering spatial data: Analysis and implementation of methods using the Voronoi diagram. Ph.D. dissertation Brown Univ. Providence R.I.
HUTTENLOCHER D. P., 1991, Proceedings of the 7th Annual ACM Symposium on Computational Geometry, 194-203
IMAI H., 1985, Voronoi diagram in the Laguerre geometry and its applications, SIAM J. Comput., 14, 93, 10.1137/0214006
IMAI~ K., 1989, Proceedings of the 5th Annual ACM Symposium on Computational Geometry., 266
JOHNSON W. A., 1939, Reaction kinetics in processes of nucleation and growth, Trans. Am. Instit. Mining Metall. A.LM.M.E., 135, 416
KANTABUTRA V., 1983, Traveling salesman cycles are not always subgraphs of Voronoi duals, Inf. Process. Lett., 16, 11, 10.1016/0020-0190(83)90004-2
KEEL J. M., 1989, The Delaunay triangulation closely approximates the complete Euclidean graph, Springer LNCS, 382, 47
KL~NG T., 1966, Random fragmentation in two and three dimensions, Z. Astrophysik, 64, 433
KPATRICK D. G., 1979, Proceedings of the 20th Annual IEEE Symposium on FOCS., 18
KPATRICK D. G., 1980, A note on Delaunay and optimal triangulations, Inf Process. Lett., 10, 127, 10.1016/0020-0190(80)90062-9
KPATRICK D. G., 1983, Optimal search in planar subdivisions, SIAM J. Comput., 12, 28, 10.1137/0212002
KLEE V., 1980, On the complexity of d-dimensional Voronoi diagrams, Archiv Math., 34, 75, 10.1007/BF01224932
KLEIN R. 1989. Concrete and Abstract Voronoi D~agrams. Springer LNCS 400. KLEIN R. 1989. Concrete and Abstract Voronoi D~agrams. Springer LNCS 400.
KLEIN R., 1988, Voronoi diagrams based on general metrics in the plane, Springer LNCS, 294, 281
KNUTH D. 1973. The Art of Computer Programming III: Sorting and Searching. Addison- Wesley Reading Mass. KNUTH D. 1973. The Art of Computer Programming III: Sorting and Searching. Addison- Wesley Reading Mass.
E., 1973, Wirkungsbereichspolyeder und Wirkungsbereichsteilungen zu kubischen Gitterkomplexen mit weniger als drei Freiheitsgraden, Z. Kristallograph., 138, 196, 10.1524/zkri.1973.138.138.196
KO EC, R, 1963, An alternative method for the construction of Thiessen polygons, Professional Geographer, 15, 24, 10.1111/j.0033-0124.1963.024_r.x
KUUSKAL J. B., 1956, On the shortest spanning subtree of a graph and the traveling salesman problem, Problem. Am. Math. Soc., 7, 48, 10.1090/S0002-9939-1956-0078686-7
LANTUEJOUL C., 1984, Geodesic methods in quantitative image analysis, Pattern Recogn., 17, 177, 10.1016/0031-3203(84)90057-8
LAVES P., 1930, Ebeneneinteilung in Wirkungsbereiche, Z. Kristallograph., 76, 277
LAWSON C. L. 1972. Generation of a triangular grid with applications to contour plotting. Tech. Memorandum 299 California Inst. Tech. Jet Propulsion Lab. LAWSON C. L. 1972. Generation of a triangular grid with applications to contour plotting. Tech. Memorandum 299 California Inst. Tech. Jet Propulsion Lab.
LAWSON C. L. 1977. Software for C1 surface interpolation. In Mathematical Software III J. Rice Ed. Academic Press New York. LAWSON C. L. 1977. Software for C1 surface interpolation. In Mathematical Software III J. Rice Ed. Academic Press New York.
LEE D. T., 1982, On k-nearest neighbor Voronoi diagrams in the plane, IEEE Trans. Comput. C-31,478-487.
LEE D. T., 1982, Medial axis transform of a planar shape, IEEE Trans. Patt. Anal. Mach. Intell. PAMI-4, 363, 10.1109/TPAMI.1982.4767267
LEE D. T., 1981, Generalization of Voronoi diagrams in the plane, SIAM J. Comput., 10, 73, 10.1137/0210006
LEE D. T., 1986, Generalized Delaunay triangulation for planar graphs, Discrete Comput. Geom., 1, 201, 10.1007/BF02187695
LEE D. T., 1984, Computational geometry--A survey, IEEE Trans. Cornput. C., 33, 1072, 10.1109/TC.1984.1676388
LEE D. T., 1980, Two algorithms for constructing a Delaunay triangulation, Int. J. Comput. Inf. Sci., 9, 219, 10.1007/BF00977785
LEE D. T., 1980, Voronoi diagrams in the Ll(L~) metrics with 2- dimensional storage applications, SIAM J. Comput., 9, 200, 10.1137/0209017
LEE D. T., 1979, Location of multiple points in a planar subdivision, Inf. Process. Lett., 9, 190, 10.1016/0020-0190(79)90066-8
LEVEN D., 1986, Intersection and proximity problems and Voronoi diagrams, Adv. Robotics, 1, 187
LE, 1987, Planning a purely translational motion of a convex robot in two-dimensional space using Voronoi diagrams, Discrete Comput. Geom., 2, 9, 10.1007/BF02187867
LINGAS A. 1986b. A fast algorithm for the generalized Delauuay triangulation. Manuscript Univ. of LinkSping Sweden. LINGAS A. 1986b. A fast algorithm for the generalized Delauuay triangulation. Manuscript Univ. of LinkSping Sweden.
LITTLE D. V., 1974, A third note on recent research in geometric probability, Adv. Appl. Probab., 6, 103, 10.2307/1426209
LOEB A. L., 1970, A systematic survey of cubic crystal structures, J. Solid State Chem., 237, 10.1016/0022-4596(70)90021-6
MANACHER G. K., 1979, Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation, Inf. Process. Lett., 9, 31, 10.1016/0020-0190(79)90104-2
MATULA D. W., 1980, Properties of Gabriel graphs relevant to geographic variation research and the clustering of points in the plane, Geograph. Anal., 12, 205, 10.1111/j.1538-4632.1980.tb00031.x
MATZKE E. B., 1946, Volumeshape relationships in variant foams, Am. J. Botanics, 33, 130
MAUS A., 1884, Delaunay triangulation and the convex hull of n points in expected linear time, BIT, 24, 151, 10.1007/BF01937482
MAXWELL J. C., 1864, On reciprocal diagrams and diagrams of forces, Phil. Mag., 4, 250, 10.1080/14786446408643663
LAIN D. H., 1976, Two dimensional interpolation from random data, Comput. J., 19, 178, 10.1093/comjnl/19.2.178
MEGIDDO N., 1983, Linear time algorithms for linear programming in R3 and related problems, SlAM J. Comput., 12, 759
MEHLHORN K., 1990, On the construction of abstract Voronoi diagrams, Springer LNCS, 415, 227
MEIJERING J. L., 1953, Interface area, edge length, and number of vertices in crystal aggregates with random nucleation, Philips Res. Rept., 8, 270
MILES R. E., 1970, On the homogenous planar Poisson process, Math. Biosci., 6, 85, 10.1016/0025-5564(70)90061-1
MOLLISON D., 1977, Spatial contact models for ecological and epidemic spread, J. Roy. Stat. Soc. B, 39, 283, 10.1111/j.2517-6161.1977.tb01627.x
MORAN P. A., 1966, A note on recent research in geometric probability, J. Appl. Probab., 3, 53, 10.1017/S0021900200114251
MORAN P. A., 1969, A second note on recent research in geometrical probability, Adv. Appl. Probab., 1, 73, 10.2307/1426409
MOUNT D. M. 1985. Voronoi diagrams on the surface of a polyhedron. Rep. 1496 Univ. of Maryland. MOUNT D. M. 1985. Voronoi diagrams on the surface of a polyhedron. Rep. 1496 Univ. of Maryland.
MOUNT D. M., 1986, Proceedings of the 2nd Annual ACM Symposium on Computational Geometry., 150, 10.1145/10515.10532
MOUNT D., 1988, Proceedings of the 4th Annual ACM Symposium on Computational Geometry., 143, 10.1145/73393.73408
MUDER D. J. 1988a. How big is an n-sided Voronoi polygon? Manuscript MITRE Corp. Bedford Mass. MUDER D. J. 1988a. How big is an n-sided Voronoi polygon? Manuscript MITRE Corp. Bedford Mass.
MUDER D. J., 1988, Putting the best face on a Voronoi polyhedron, Proc. London Math. Soc., 56, 329, 10.1112/plms/s3-56.2.329
MULMULEY K. 1991. On levels in arrangements and Voronoi diagrams. Discrete Comput. Geom. In press. 10.1007/BF02574692 MULMULEY K. 1991. On levels in arrangements and Voronoi diagrams. Discrete Comput. Geom. In press. 10.1007/BF02574692
MURTADH F., 1983, A survey of recent advances in hierarchical clustering algorithms, Computer J., 26, 354, 10.1093/comjnl/26.4.354
NEWMAN C. M., 1983, Nearest neighbor and Voronoi regions in certain point processes, Adv. Appl. Probab., 15, 726, 10.2307/1427321
NIGGLI R., 1927, Die topologische Strukturanalyse, Z. KristaUograph., 65, 391
NOWACKI W., 1933, Der Begriff 'Voronoischer Bereich, Z. Kristallograph., 85, 331
NOWACKI W., 1976, Uber allgemeine Eigenschaften von Wirkungsbereichen, Z. KristaUograph., 143, 360
O'DUNLAING C., 1985, A "retraction'' method for planning the motion of a disc, J. Algorithms, 6, 104, 10.1016/0196-6774(85)90021-5
O'DUNLAING C., 1986, Generalized Voronoi diagrams for moving a ladder: I. Topological analysis, Comm. Pure Appl. Math., 39, 423, 10.1002/cpa.3160390402
O'DUNLAING C., 1987, Generalized Voronoi diagrams for moving a ladder: II. Efficient construction of the diagram, Algorithmica, 2, 27, 10.1007/BF01840348
OHYA T., 1984, Improvements of the incremental methods for the Voronoi diagram with computational comparison of various algorithms, J. Operations Res. Soc. Japan, 27, 306, 10.15807/jorsj.27.306
OKABE A., 1988, The statistical analysis of a distribution of active points in relation to surface-like elements, Environ. Plan. A, 20, 609, 10.1068/a200609
OVERMARS M., 1981, Dynamization of order decomposable set problems, J. Algorithms, 2, 245, 10.1016/0196-6774(81)90025-0
PACH J., 1989, The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates, Discrete Comput. Geom., 4, 291, 10.1007/BF02187732
PAPADTMITRIOU C. H., 1977, The Euclidean traveling salesman problem is NP-complete, Theor. Comp. Sci., 4, 237, 10.1016/0304-3975(77)90012-3
PASCHINGER I. 1982. Konvexe Polytope und Dirichletsche Zellenkomplexe. Ph.D. Dissertation Inst. f Math. Univ. Salzburg Austria. PASCHINGER I. 1982. Konvexe Polytope und Dirichletsche Zellenkomplexe. Ph.D. Dissertation Inst. f Math. Univ. Salzburg Austria.
PmLBRICK 0. 1968. Shape recognition with the medial axis transform. In P~ctorial Pattern Reeognitwn G. C. Cheng R. S. Ledley D. K Pollock and A. Rosenfeld Eds. Washington D.C. PmLBRICK 0. 1968. Shape recognition with the medial axis transform. In P~ctorial Pattern Reeognitwn G. C. Cheng R. S. Ledley D. K Pollock and A. Rosenfeld Eds. Washington D.C.
PRE RATA, 1977, Ill., pp, 23-24
PRIM R. C., 1957, Shortest connection networks and some generalizations Bell, Syst. Tech. J., 36, 1389, 10.1002/j.1538-7305.1957.tb01515.x
RAJAN V. T., 1991, Proceedings of the 7th Annual ACM Symposium on Computational Geometry, 357, 10.1145/109648.109688
RHYNSBURGER D., 1973, Analytical delineation of Thiessen polygons, Geograph. Anal., 5, 133, 10.1111/j.1538-4632.1973.tb01003.x
ROGERS C. A. 1964. Packing and Covering. Cambridge University Press London New York. ROGERS C. A. 1964. Packing and Covering. Cambridge University Press London New York.
ROHNERT H., 1988, Moving discs between polygons, Springer LNCS, 317, 502
ROSENBERCER H. 1988. Order-k Voronoi diagrams of sites with additive weights in the plane. Rep. UIUCDCS-R-88-1431 Dept. Cornput. Sci. Univ. Illinois Urbana Ill. ROSENBERCER H. 1988. Order-k Voronoi diagrams of sites with additive weights in the plane. Rep. UIUCDCS-R-88-1431 Dept. Cornput. Sci. Univ. Illinois Urbana Ill.
ROSENKRANTZ D. J., 1977, An analysis of several heuristics for the traveling salesman problem, SIAM J. Comput., 6, 563, 10.1137/0206041
ROWAT P. F. 1979. Representing spatial experience and solving spatial problems in a simulated robot environment. Ph.D. dissertation Univ. of British Columbia Canada. ROWAT P. F. 1979. Representing spatial experience and solving spatial problems in a simulated robot environment. Ph.D. dissertation Univ. of British Columbia Canada.
SAI MOTO, 1988, Patterns of weighted Voronoi tessellations, Sct. Form, 3, 103
SCH()NFLIES A. 1891. Kristallsysteme und Kirstallstruktur. Teubner Leipzig. SCH()NFLIES A. 1891. Kristallsysteme und Kirstallstruktur. Teubner Leipzig.
SCHWARTZ J. AND YAP C. K. 1986. Advances in Robotics. Lawrence Erlbaum Associates Hillside N.J. SCHWARTZ J. AND YAP C. K. 1986. Advances in Robotics. Lawrence Erlbaum Associates Hillside N.J.
SCHWARZKOPF O., 1989, Parallel computation of discrete Voronoi diagrams, Springer LNCS, 349, 193
SEIDEL R. 1981. A convex hull algorithm optimal for point sets in even dimensions. Rep. 81-14 Univ. of Britmh Columbia Vancouver Canada. SEIDEL R. 1981. A convex hull algorithm optimal for point sets in even dimensions. Rep. 81-14 Univ. of Britmh Columbia Vancouver Canada.
SEIDEL R., 1982, Proceedings of the 20th Annual Allerton Conference on CCC., 94
SEIDEL R. 1985 A method for proving lower bounds for certain geometric problems. In Computational Geometry G. T. Toussaint Ed. pp. 319-334. SEIDEL R. 1985 A method for proving lower bounds for certain geometric problems. In Computational Geometry G. T. Toussaint Ed. pp. 319-334.
SEIDEL R., 1986, Proceedings of the 18th Annual ACM Symposium on STOC., 404
SE EL, R, 1987, Proceedings of the 3rd Annual Symposium on Computational Geometry., 181
SEIDEL R., 1988, IIG-TU Graz, 178
SHAMOS M. I., 1975, Proceedings of the 7th Annual ACM Symposium on STOC., 224
SRAMOS M. I. 1978. Computational geometry. Ph.D. dissertation Yale Univ. New Haven Conn. SRAMOS M. I. 1978. Computational geometry. Ph.D. dissertation Yale Univ. New Haven Conn.
SR MOS, 1975, Proceedings of the 16th Annual IEEE Symposium on FOCS, 151
SHAR, 1985, Intersection and closest-pair problems for a set of planar discs, SIAM J. Comput., 14, 448, 10.1137/0214034
R., 1977, Locally equiangular triangulations, Comput. J., 21, 243
R., 1979, The Dirichlet tessellation as an aid in data analysis, Scandinavian J. Stat., 7, 14
R., 1980, A vector identity for the Dlrichlet tessellation, Math. Proc. Camb. Phil. Soc., 87, 151, 10.1017/S0305004100056589
SIFRONY S., 1986, Proceedings of the 2nd Annual ACM Symposium on Computational Geometry., 178, 10.1145/10515.10535
SMITH C. S., 1954, The shape of things. Sci, Am., 58
SNYDE, 1962, Urban places in Uruguay and the concept of a hierarchy. Festschrift, C. F. Jones. Northwestern University Studies in Geography, 6, 29
STIFTER S. 1989. An axiomatic approach to Voronoi diagrams in 3D. Manuscript RISC Univ. of Linz Austria. STIFTER S. 1989. An axiomatic approach to Voronoi diagrams in 3D. Manuscript RISC Univ. of Linz Austria.
SUGISARA K. AND IRI M. 1988. Geometric algorithms in finite-precision arithmetic. Research Memorandum RMI 88-10 Faculty of Engineering Univ. of Tokyo Japan. SUGISARA K. AND IRI M. 1988. Geometric algorithms in finite-precision arithmetic. Research Memorandum RMI 88-10 Faculty of Engineering Univ. of Tokyo Japan.
SUZUKI A., 1986, Approximation of a tessellation of the plane by a Voronoi diagram, J. Operations Res. Soc. Japan, 29, 69, 10.15807/jorsj.29.69
TANEMURA M., 1983, A new algorithm for three-dimensional Voronoi tessellation, J. Comput. Phys., 51, 191, 10.1016/0021-9991(83)90087-6
T~SKI A. 1951. A decision method for elementary algebra and geometry. Univ. of California Press Berkeley Calif. T~SKI A. 1951. A decision method for elementary algebra and geometry. Univ. of California Press Berkeley Calif.
TH SSEN, 1911, Precipitation average for large area, Monthly Weather Rev., 39, 1082, 10.1175/1520-0493(1911)39<1082b:PAFLA>2.0.CO;2
TOKUYAMA T. 1988. Deformation of merged Voronoi diagrams with translation. Rep. TR- 88-0049 IBM Tokyo Research Lab. TOKUYAMA T. 1988. Deformation of merged Voronoi diagrams with translation. Rep. TR- 88-0049 IBM Tokyo Research Lab.
TOUSSA~NT G. T., 1980, The relative neighborhood graph of a finite planar set, Pattern Recogn., 12, 261, 10.1016/0031-3203(80)90066-7
TOUSSAINT G. T. ANn BHATTACHARYA B. K. 1981. On geometric algorithms that use the furthestpoint Voronoi diagram. Rep. 81-3 McGill Univ. Montreal Quebec Canada. TOUSSAINT G. T. ANn BHATTACHARYA B. K. 1981. On geometric algorithms that use the furthestpoint Voronoi diagram. Rep. 81-3 McGill Univ. Montreal Quebec Canada.
TUOMIN~N O., 1949, Das EinfiuBgebeit der Stadt Turku ins System der Einfiuflgebiete SW--Finnlands, Fennia, 71, 1
URQUHART R. 1980. A note on the computation of subgraphs of the Delaunay triangulation. Rep. Univ. of Glasgow U.K. URQUHART R. 1980. A note on the computation of subgraphs of the Delaunay triangulation. Rep. Univ. of Glasgow U.K.
VAIDYA P. M., 1988, Proceedings of the 20th Annual ACM Symposium on STOC., 422
VORONOI M. G., 1908, Nouvelles applications des parametres continus a la theorie des formes quadratiques, J. Reine Angew. Math., 134, 198, 10.1515/crll.1908.134.198
WANG C. A., 1987, Proceedings of the 3rd Annual ACM Symposium on Computational Geometry., 223
WATSON D. F., 1981, Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes, Comput. J., 24, 167, 10.1093/comjnl/24.2.167
WEA E, D, 1984, Soap, cells, and statistics--random patterns in two dimensions, Contemp. Phys., 25, 59, 10.1080/00107518408210979
TELEY W., 1979, Realizability of polyhedra, Structural Topol., 1, 46
WIGNER E., 1933, On the constitution of metallic sodium, Phys. Rev., 43, 804, 10.1103/PhysRev.43.804
LIAMS R. E., 1968, Space-filling polyhedron: Its relation to aggregates of soap bubbles, plant cells, and metal crystalites, Science, 161, 276, 10.1126/science.161.3838.276
YAO A. C., 1975, An O(E log log V) algorithm for finding minimum spanning trees, Inf. Process. Lett., 4, 21, 10.1016/0020-0190(75)90056-3
YAO A. C., 1982, On constructing minimum spanning trees in k-dimensional spaces and related problems, SIAM J. Comput., 11, 721, 10.1137/0211059