Franz Aurenhammer
- AGARWAL, P. K., EDELSBRUNNER, H., SCHWARZKOPF, O., AND WELZL, E. 1990. Euclidean minimum spanning trees and bicromatic closest pairs. In Proceedings of the 6th Annual ACM Symposium on Computational Geometry, pp. 203-210. Google Scholar
- AGGARWAL, A., AND SURI, S. 1987. Fast algorithms for computing the largest empty rectangle. In Proceedings of the 3rd Annual ACM Symposium on Computational Geometry, pp. 278-290. Google Scholar
- AGGARWAL, A., HANSEN, M., ANn LEIGHTON, T. 1990. Solving query retrieval problems by compacting Voronoi diagrams. In Proceedings of the 22nd Annual ACM Symposium on STOC, pp. 331-340. Google Scholar
- AGGARWAL, A., GUIBAS, L. J., SAXE, J., AND SHOR, P. W. 1989a. A linear time algorithm for computing the Voronoi diagram of a convex polygon. Discrete Comput. Geometry 4, 591-604. Google Scholar
- AGGARWAL, A., IMAI, H., KATOH, N., AND SURI, S. 1989b. Finding k points with minimum diameter and related problems. In Proceedings of the 5th Annual ACM Symposium on Computational Geometry, pp. 283-291. Google Scholar
- AGGARWAL, A., CHAZELLE, B., GUIBAS, L. J., O'DUNLAING, C., AND YAP, C. K. 1988. Parallel computational geometry. Algorithmica 3, 293-327.Google Scholar
- AHUJA, N. 10~2. Dot pattorn processing using Voronoi polygons as neighborhoods. IEEE Trans. Patt. Anal. Mach. Int. PAMI-4, 336-343. Google Scholar
- AKL, S. 1983 A note on Euclidean matchings, triangulations, and spanning trees. J. Comb. Inf. Syst. Sci. 8, 169-174.Google Scholar
- ALEXANDERSON, G. L., AND WETZEL, J. E. 1978. Simple partition of space. Math. Magazine 51, 220-225.Google Scholar
- ALT, H., AND YAP, C. K. 1990. Algorithmic aspects of motion planning: A tutorial (part 2). Algorithms Rev. 1, 61-77.Google Scholar
- AONUMA, H., IMAI, H., IMAI, K., AND TOKUYAMA, T. 1990. Maximin location of convex objects in a polygon and related dynamic Voronoi diagrams. In Proceedings of 6th Annual ACM Symposium on Computational Geometry. pp. 225-234. Google Scholar
- ARNOLD, D. B., AND MILNE, W. J. 1984. The use of Voronoi tessellations in processing soil survey results. IEEE Comput. Graph. Appl. 4, 22-30.Google Scholar
- ARONOV, B. 1989. On the geodesic Voronoi diagram of point sites in a simple polygon. Algorithmica 4, 109-140.Google Scholar
- ARONOV, B., FORTUNE, S., AND WILFONG, G. 1988. The furthest-site geodesic Voronoi diagram. In Proceedings of the 4th Annual ACM Symposium on Computational Geometry. pp. 229-240. Google Scholar
- ARONOV, B., CHAZELLE, B., EDELSBRUNNER, $., GUIBAS, L. J., SHARIR, M., AND WENGER, R. 1990. Points and triangles in the plane and halving planes in space. In Proceedings of the 6th Annual ACM Symposium on Computational Geometry. pp. 112-115. Google Scholar
- ASANO, T., AND ASANO, T. 1986. Voronoi diagram for points in a simple polygon. In Perspectives in Computing 15, D. S. Johnson, T. Nishizeki, A. Nozaki, H. S. Will Eds. Academic Press, New York, pp. 51-64.Google Scholar
- ASANO, T., BHATTACHARYA, B., KEIL, M., AND YAO, F. 1988. Clustering algorithms based on minimum and maximum spanning trees. In Proceedings of the 4th Annual ACM Symposium on Computational Geometry, pp. 252-257. Google Scholar
- ASH, P. F., AND BOLKER, E. D. 1985. Recognizing Dirichlet tessellations. Geometriae Dedicata 19, 175-206.Google Scholar
- ASH, P. F., AND BOLKER, E. D. 1986. Generalized Dirichlet tessellations. Geometrme Dedicata 20, 209-243.Google Scholar
- ASH, P. F., BOLKER, E. D., CRAPO, H., AND WHITE- LEY, W. 1988. Convex polyhedra, Dirichlet tessellations, and spider webs. In Shaping Space: A Polyhedral Approach, M. Senechal and G. Fleck, Ed~. Birkh/iuser, Boston, pp. 231-250.Google Scholar
- AUGENBAUM, J. M., AND PESKIN, C. S. 1985. On the construction of the Voronoi mesh on a sphere. J. Comput. Phys. 59, 177-192.Google Scholar
- AURENHAMMER, F. 1987a. Power diagrams: Properties, algorithms, and applications. SIAM J. Comput. 16, 78-96. Google Scholar
- AURENHAMMER, F. 1987b. A criterion for the affine equivalence of cell complexes in R d and convex polyhedra in Rd+ 1. Discrete Comput. Geometry 2, 49-64.Google Scholar
- AURENHAMMER, F. 1987c. Recognising polytopical cell complexes and constructing projection polyhedra. J. Symbolic Comput. 3, 249-255. Google Scholar
- AURENHAMMER, F. 1988a. Improved algorithms for discs and balls using power diagrams. J. Algorithms 9, 151-161. Google Scholar
- AURENHAMMER, F. 1988b. Linear combinations from power domains. Geometriae Dedicata 28, 45-52.Google Scholar
- AURENHAMMER, F. 1990a. A new duality result concerning Voronoi diagrams. Discrete Comput. Geometry 5, 243-254. Google Scholar
- AURENHAMMER, F. 1990b. A relationship between Gale transforms and Voronoi diagrams. Discrete Appl. Math. 28, 83-91. Google Scholar
- AURENHAMMER, F., AND EDELSBRUNNER, $. 1984. An optimal algorithm for constructing the weighted Voronoi diagram in the plane. Pattern Recognition 17, 251-257.Google Scholar
- AURENHAMMER, F., AND IMAI, H. 1988. Geometric relations among Voronoi diagrams. Geometriae Dedicata 27, 65-75.Google Scholar
- AURENHAMMER, F., AND SCHWARZKOPF, O. {1991}. A simple on-llne randomized incremental algorithm for computing higher-order Voronoi diagrams. In Proceedings of the 7th Annual ACM Symposium on Computational Geometry. pp. 142-151. Google Scholar
- AURENHAMMER, F., AND STOCKL, G. 1988. On the peeper's Voronoi diagram. Rep. 264, IIG-TU Graz, Austria.Google Scholar
- AURENHAMMER, F., ST(SCKL, G., AND WELZL, E. 1991. The post-office problem for fuzzy point sets. Rep. 91-07, FU Berlin, Germany.Google Scholar
- AVIS, D., AND BHATTACHARYA, B. K. 1983. Algorithms for computing d-dimenslonal Voronoi diagrams and their duals. Adv. Comput. Res. 1,159-180.Google Scholar
- BABENKO, V. F. 1977. On the optimal cubature ormulae on certain classes of continuous functions. Analys~s Math. 3, 3-9.Google Scholar
- BADDELEY, A. 1977. A fourth note on recent research in geometrical probability. Adv. Appl. Probab. 9, 824-860.Google Scholar
- BALTSAN, A., AND SHARm, M. 1988. On shortest paths between two convex polyhedra. J. ACM 35, 267-287. Google Scholar
- BENTLEY, J. L., AND MAURER, H. A. 1979. A note on Euclidean near neighboring searching in the plane. Inf. Process. Lett. 8, 133-136.Google Scholar
- BENTLEY, J. L., WEIDE, B. W., AND YAO, A. C. 1980. Optimal expected-time algorithms for closest-point problems. ACM Trans. Math. Sofiw. 6, 563-580. Google Scholar
- BERN, M. W., EPPSTEIN, D., AND GILBERT, J. 1990. Provably good mesh generation. Manuscript, XEROX Palo Alto Research Center, Palo Alto, Calif.Google Scholar
- BESAG, J. 1974. Spatial interaction and the statistical analysis of lattice systems. J. Roy. Statist. Soc. B 36, 192-236.Google Scholar
- BIEBERBACH, L. 1912. 'l)ber die Bewegungsgruppen der euklidischen Riiume I, II. Math. Ann. 72, 400-412.Google Scholar
- BLUM, H. 1967. A transformation for extracting new descriptors of shape. In Proceedings of the Symposium on Models for the Perception of Speech and Visual Form. Weiant Whaten- Dunn, Ed. MIT Press, Cambridge, Mass., pp. 362-380.Google Scholar
- BLUM, H. 1973. Biological shape and visual science (Part I). J. Theol'. Biol. 38, 205-287.Google Scholar
- BOISSONNAT, J.-D. 1988. Shape recognition from planar cross sections. Comput. Vision Graph. and Image Process. 44, 1-29. Google Scholar
- BOISSONNAT, J.-D., AND TEILLAUD, M. 1986. A hierarchical representation of objects: The Delaunay tree. In Proceedings of 2nd Annual ACM Symposium on Computational Geometry, pp. 260-268. Google Scholar
- BOOTS, B. N. 1979. Weighting Thiessen polygons. Econ. Geography, 248-259.Google Scholar
- BooTs, B. N. 1986. Voronoi (Thiessen) polygons. In CATMOG 45, Geo Books, Norwich, Conn.Google Scholar
- BOWYER, A. 1981. Computing Dirichlet tessellations. Computer J. 24, 162-166.Google Scholar
- BRASSEL, K. E., AND REIF, D. 1979. A procedure to generate Thiessen polygons. Geograph. Anal. 11,289-303.Google Scholar
- BR~SSON, E. 1989. Representing geometric structures in d dimensions: Topology and order. In Proceedings of the 5th Annual ACM Symposium on Computational Geometry. pp. 218-227. Google Scholar
- BRONDSTED, A. 1983. An Introduction to Convex Polytopes. Springer, New York, Heidelberg, Berlin.Google Scholar
- BRosTow, W., AND SICOTTE, Y. 1975. Coordination number in liquid argon. Physica A 80, 513-522.Google Scholar
- BROSTOW, W., DUSSAULT, J. P., AND FOX, B. L. 1978. Construction of Voronoi polyhedra. J. Comput. Phys. 29, 81-92.Google Scholar
- BROWN, K. Q. 1979. Voronoi diagrams from convex hulls. Inf. Process. Lett. 9,223-228.Google Scholar
- BROWN, K. Q. 1980. Geometric transforms for fast geometric algorithms. Ph.D. dissertation, Carnegie-Mellon Univ., Pittsburgh, Penn. Google Scholar
- BRUMBERGER, H. AND GOODISMAN. 1983. Voronoi cells: An interesting and potentially useful cell model for interpreting the small angle scattering of catalysts. J. Appl. Crystallogr. 16, 83-88.Google Scholar
- CALABI, L., AND HARTNETT, W.E. 1968. Shape recognition, prairie fires, convex deficiencies, and skeletons. Am. Math. Monthly 75, 335-342.Google Scholar
- CANNY, J., AND DONALD, B. 1988. Simplified Voronoi diagrams. Discrete Comput. Geom. 3, 2 19-236. Google Scholar
- CHAZELLE, B. 1985. How to search in history. Inf. Control 64, 77-99. Google Scholar
- CHAZ~LLE, B., AND EDELSBRUNNER, H. 1987. An improved algorithm for constructing kth-order Voronoi diagrams. IEEE Trans. Comput. C-36, 1349-1354. Google Scholar
- CHAZELLE, B., AND PREPARATA, F. P. 1986. Hall space range search: an algorithmic application of k-sets. Discrete Comput. Geom. 1, 83-94. Google Scholar
- CHAZELLE, B., DRYSDALE, R. L., LEE, D. T. 1986a. Computing the largest empty rectangle. SIAM J. Comput. 15, 300-315. Google Scholar
- CHAZELLE, B., COLE, R., PREPARATA, F. P., AND YAP, C. K. 1986b. New upper bounds for neighbor searching. Inf. Control 68, 105-124. Google Scholar
- CHAZELLE, B., EDELSBRUNNER, H., GUIBAS, L. J., HERSHBERGER, J. E., SEIDEL, R., AND SHARIR, M. 1990. Slimming down by adding; selecting heavily covered points. In Proceedings of the 6th Annual ACM Symposium on Computational Geometry, pp. 116-127. Google Scholar
- CHrR~TON, D., AND TARJAN, R. E. 1976. Finding minimum spanning trees. SIAM J. Comput. 5, 724-742.Google Scholar
- CHEW, L. P. 1986. There is a planar graph almost as good as the complete graph. In Proceedings of the 2nd Annual ACM Symposium on Computational Geometry. pp. 169-177. Google Scholar
- CHEW, L. P. 1989a. Constrained Delaunay triangulations. Algorithmica 4, 97-108.Google Scholar
- HEW, L. P. 1989b. Guaranteed-quality triangular meshes. Rep. TR 89-983, Dept. Comput. Sci., Cornell Univ., Ithaca, N.Y.Google Scholar
- CHEW, L. P., AND DRYSDALE, R. L. 1985. Voronoi diagrams based on convex distance functions. In Proceedings of the 1st Annual ACM Symposium on Computational Geometry. pp. 235-244. Google Scholar
- CHEW, L. P., AND KEDEM, K. 1989. Placing the largest similar copy of a convex polygon among polygonal obstacles. In Proceedings of the 5th Annual ACM Symposium on Computational Geometry. pp. 167-174. Google Scholar
- Chow, A. 1980. Parallel algorithms for geometric problems. Ph.D. dissertation. Dept. Comput. Sci., Univ. of Illinois, Urbana, Ill. Google Scholar
- CI~ISTOFIDES, N. 1976. Worst-case analysis of a new heuristic for the traveling salesman problem. Symposium on Algorithms and Complexity, Carnegie-Mellon Univ., Penn.Google Scholar
- CLARKSON, K. L. 1987. New applications of random sampling to computational geometry. Discrete Comput. Geom. 2, 195-222.Google Scholar
- CLARKSON, K. L. 1989. An algorithm for geometric minimum spanning trees requiring nearly linear expected time. Algorithmica4, 461-468.Google Scholar
- CLARKSON, K. L., AND SHOR, P. W. 1988. Algorithms for diametral pairs and convex hulls that are optinml, randomized, and incremental. In Proceedings of the 4th Annual ACM Symposium on Computational Geometry. pp. 12-17. Google Scholar
- CLARKSON, K. L., AND SHOR, P. W. 1989. Applica~ tions of random sampling in computational geometry, II. Discrete Comput. Geom. 4, 387-421. Google Scholar
- COLE, R., GOODRICH, M. T., AND O'DUNLAING, C. 1990. Merging free trees in parallel for efficient Voronoi diagram construction. Springer LNCS 443, pp. 432-445. Google Scholar
- CONWAY, J. M., AND SLOAN~, N. J. A. 1982. Voronoi regions of lattices, second moments of polytopes, and quantization. IEEE Trans. Inf. Theory IT-28, 211-226.Google Scholar
- CRAIg, L. K. 1978. The Monte Carlo generation of random polygons. Comput. Geosci. 4, 131-141.Google Scholar
- CRAPO, H. 1979. Structural rigidity. Struct. Topol. 1, 13-45.Google Scholar
- CRuz ORIVE, L.-M. 1979. Distortion of certain Voronoi tessellations when one particle moves. J. Appl. Probab. 16, 95-103.Google Scholar
- DAVID, E. E., A~D DAVID, C. W. 1982. Voronoi polyhedra as a tool for studying solvation structure. J. Chem. Phys. 76, 4611-4614.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- DEHNE, F., AND NOLTEMEIER, H. 1985. A computational geometry approach to clustering problems. In Proceedings of the 1st Annual ACM Symposium on Computational Geometry. pp. 245-250. Google Scholar
- DELAUNAY, B. N. 1932. Neue Darstellung der geometrischen Kristallographie. Z. Kristallograph. 84,109-149.Google Scholar
- DELAUNAY, B. N. 1934. Sur la sphere vide. Bull. Acad. Science USSR VII: Class. Sci. Math., 793-800.Google Scholar
- 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-31.Google Scholar
- DELAUNAY, B. N., DOLBILIN, N. P., AND STOGRIN, M. I. 1978. Combinatorial and metric theory of planigons. Trudy Mat. Inst. Steklov 148, 109-140.Google Scholar
- DEWDNEY, A. K. 1977. Complexity of nearest neighbour searching in three and higher dimensions. Rep. 28, Univ. of Western Ontario, London, Ontario.Google Scholar
- DEWDNEY, A. K., AND VRANCH, J. K. 1977. A convex partition of R3 with applications to Crum's problem and Knuth's post-office problem. Util. Math. 12, 193-199.Google Scholar
- DILLENCOURT, M. B. 1987a. Traveling salesman cycles are not always subgraphs of Delaunay triangulations. Inf. Process. Lett. 24, 339-342. Google Scholar
- DILLENCOURT, M. B. 1987b. A non-Hamiltonian, nondegenerate Delaunay triangulation. Inf. Process. Lett. 25, 149-151. Google Scholar
- DILLENCOURT, M. B. 1987c. Toughness and Delaunay triangulations. In Proceedings of the 3rd Annual ACM Symposium on Computational Geometry. pp. 186-194. Google Scholar
- DIRICHLET, G. L. 1850. Uber die Reduction der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen. J. Re~ne u. Angew. Math. 40, 209-227.Google Scholar
- DOBKIN, D. P., AND LASZLO, M. J. 1989. PrimL tives for the manipulation of three-dimensional subdivisions. Algorithmica 4, 3-32.Google Scholar
- DOBKIN, D. P., AND LmTON, R. J. 1976. Multidimensional searching problems. SIAM J. Comput. 5, 181-186.Google Scholar
- DOBKIN, D. P., FRIEDMAN, S., AND SUPOWIT, K. 1990. Delaunay graphs are almost as good as complete graphs. Discrete Comput. Geom. 5, 399-407. Google Scholar
- DRYSDALE, R. L. 1990. A practical algorithm for computing the Delaunay triangulation for convex distance functions. In Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 159-168. Google Scholar
- DWYER, R. A. 1987. A faster divide-and-conquer algorithm for constructing Delaunay triangulations. Algorithmica 2, 137-151.Google Scholar
- DWYER, R. A. 1989. Higher-dimensional Voronoi diagrams in linear expected time. In Proceedings of the 5th Annual ACM Symposium on Computational Geometry. pp 326-333. Google Scholar
- EDAHIRO, M., KOKUBO, I., AND ASANO, T. 1984. A new point-location algorithm and its practical efficiency: Comparison with existing algorithms. ACM Trans. Graph. 3, 86-109. Google Scholar
- EDELSBRUNNER, H 1986 Edge-skeletons in arrangements with applications. AlgorLthmica 1, 93-109. Google Scholar
- EDELSBRUNNER, H. 1987. Algorithms in Combinatorial Geometry. Springer, Berlin-Heidelberg. Google Scholar
- EDELSBRUNNER, a. 1989. An acyclicity theorem for cell complexes in d dimensions. In Proceedings of the 5th Annual ACM Symposium on Computational Geometry. pp. 145-151. Google Scholar
- EDELSBRUNNER, H., AND MAURER, H. A. 1985. Finding extreme points in three dimensions and solving the post-office problem in the plane. Inf. Process. Lett. 21, 39-47.Google Scholar
- EDELSBRUNNER, H., AND SEIDEL, R. 1986. Voronoi diagrams and arrangements. Discrete Comput. Geom. 1, 25-44. Google Scholar
- EDELSBRUNNER, H., AND WELZL, E. 1985. On the number of line separations of a finite set in the plane. J. Combin. Theory Ser. A, 15-29.Google Scholar
- EDELSBRUNNER, H., GUIBAS, L. J., AND S~A~m, M. 1989. The upper envelope of piecewise linear functions: algorithms and applications. Discrete Comput. Geom. 4, 311-336.Google Scholar
- EDELSBRUNNER, H., GUmAS, L. J., STOLFI, J. 1986. Optimal point location in a monotone subdivision. SIAM J. Comput. 15, 317-340. Google Scholar
- EDELSBRUNNER, H., KIRKPATRICK, D. G., AND SEIDEL, R. 1983. On the shape of a set of points in the plane. IEEE Trans. Inf. Theory IT-29,551-559.Google Scholar
- EDELSBRUNNER, H., O'RoURKE, J., AND SEIDEL, R. 1986. Constructing arrangements of lines and hyperplanes with applications. SIAM J. Cornput. 15, 341-363. Google Scholar
- EDELSBRUNNER, H., ROTE, G., AND WELZL, E. 1987. Testing the necklace condition for shortest tours and optimal factors in the plane. Springer LNCS 267, 364-375. Google Scholar
- EHRLICH, P. E., AND IM HOF, H. C. 1979. Dirichlet regions in manifolds without conjugate points. Comment. Math. Helvet. 54,642-658.Google Scholar
- EISELT, H. A., AND PEDERZOLI, G. 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-115.Google Scholar
- ENGEL, P. 1981. 'lJber Wirkungsbereichsteilungen mit kubischer Symmetrie. Z. Kristallograph. 154, 199-215.Google Scholar
- EPPSTE~N, D. 1990. Finding the k smallest spanning trees. Springer LNCS 447, 38-47. Google Scholar
- FAIRFIELD, J. 1979. Contoured shape generation: Forms that people see in dot patterns. In Proceedings of the IEEE Conference on Systems Man Cybernetics. pp. 60-64.Google Scholar
- FAIRFIELD, J. 1983. Segmenting dot patterns by Voronoi diagram concavity. IEEE Trans. Part. Anal. Mach. Int. PAMI-5, 104-110.Google Scholar
- FEDEROFF, E. S. 1885. Elemente der Lehre yon den Figuren. Verh. Russ Min. Ges. St. Petersburg 21, 1-279.Google Scholar
- FIELD, D. A. 1986. Implementing Watson's algorithm in three dimensions. In Proceedings of the 2nd Annual ACM Symposium on Computational Geometry. pp. 246-259. Google Scholar
- FINNEY, J. L. 1979. Procedure for the construction of Voronoi polyhedra. Note. J. Comput. Phys. 32, 137-143.Google Scholar
- FORTUNE, S. 1985. A fast algorithm for polygon containment by translation. Springer LNCS 194, 189-198. Google Scholar
- FORTUNE, S. 1987. A sweepline algorithm for Voronoi diagrams. Algorithmica 2, 153-174.Google Scholar
- FORTUNE, S. 1988. Sorting helps for Voronoi diagrams. Manuscript, ATT Bell Lab., Murray Hill, N.J.Google Scholar
- FRANK, F. C., AND KASPER, J. S. 1958. Complex alloy structures regarded as sphere packings. Acta Crystallogr. 11,184-190.Google Scholar
- GABRIEL, K. R, AND SOKAL, R. R. 1969. A new statistical approach to geographic variation analysis. Syst. Zoology 18, 259-278.Google Scholar
- 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.Google Scholar
- GAREY, M. R., GRAHAM, R. L., AND JOHNSON, D. S. 1976. Some NP-complete geometric problems. In Proceedings of the 8th Annual ACM Symposium on STOC. pp. 10-22. Google Scholar
- 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-320.Google Scholar
- GILBERT, E. N. 1962. Random subdivisions of space into crystals. Ann. Math. Star. 33, 958-972.Google Scholar
- GOODRICH, M. T., O'DUNLAING, C., AND YAP, C. K. 1989. Constructing the Voronoi diagram of a set of line segments in parallel. Springer LNCS 382, 12-23. Google Scholar
- GOWDA, I. G., KIRKPATRICK, D. G., LEE, D. T., AND NAAMAD, A. 1983. Dynamic Voronoi diagrams. IEEE Trans. Inf Theory IT-29, 724-731.Google Scholar
- GREEN, P. J., AND SIBSON, R. 1977. Computing Dirichlet tesselations in the plane. Comput. J. 21, 168-173.Google Scholar
- GRUBER, P. M., AND LEKKERKERKER, C. G. 1988. Geometry of Numbers. North-Holland Publishing Co., Amsterdam.Google Scholar
- GRUBER, P. M., AND RYSKOV, S. S. 1987. Facet-tofacet implies face-tofface. Manuscript.Google Scholar
- GRfiNBAUM, B. 1967. Convex Polytopes. Interscience, New York.Google Scholar
- GRfJNBAUM, B., AND SHErHARD, G. C. 1980. Tilings with congruent tiles. Bull. Am. Math. Soc. 3, 951-973.Google Scholar
- GRUNBAUM, B., AND SHEPHARD, G. C. 1987. Tilings and Patterns. Freeman and Co., New York. Google Scholar
- GUIBAS, L. J., AND STOLFI, J. 1985. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Trans. Graph. 4, 74-123. Google Scholar
- GUIBAS, L. J., KNUTH, D. E., AND SHARIR, M. 1990. Randomized incremental construction of Delaunay and Voronoi diagrams. Springer LNCS 443, 414-431. Google Scholar
- GUIBAS, L. J., MITCHELL, J. S. B., AND ROOS, T. 1991. Voronoi diagrams of moving points in the plane. Springer LNCS. In press.Google Scholar
- HARTIGAN, J. A. 1975. Clustering Algorithms. John Wiley, New York. Google Scholar
- HEUSINGER, H., AND NOLTEMEIER, H. 1989. On separable clusterings. J. Algorithms 10, 212-227. Google Scholar
- HINRICHS, K., NIEVERGELT, J., SCHORN, P. 1988a. Plane-sweep solves the closest pair problem elegantly. Inf. Process. Lett. 26, 255-261. Google Scholar
- HLNRICHS, K., NIEVERGELT, J., SCHORN, P. 1988b. A sweep algorithm for the all-nearestneighbors problem. Springer LNCS 333, 43-54. Google Scholar
- HORTON, R. E. 1917. Rational study of rainfall data make~ possible bettor estimates of water yield. Eng. News-Record, 211-213.Google Scholar
- 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.Google Scholar
- HUTTENLOCHER, D. P., KEDEM, K., AND SHARIR, M. 1991. The upper envelope of Voronoi surfaces and its applications. In Proceedings of the 7th Annual ACM Symposium on Computational Geometry, 194-203. Google Scholar
- HWANG, F. K. 1979. An O(nlog n) algorithm for rectilinear minimal spanning trees. J. ACM 26, 177-182. Google Scholar
- IMAI, H., IRI, M., AND MUROTO, K. 1985. Voronoi diagram in the Laguerre geometry and its applications. SIAM J. Comput. 14, 93-105.Google Scholar
- IMAI~ K., SUMINO, S., IMAI, H. 1989. Minimax geometric fitting of two corresponding sets of points. In Proceedings of the 5th Annual ACM Symposium on Computational Geometry. pp. 266-275. Google Scholar
- JOHNSON, W. A., AND MEHL, R. F. 1939. Reaction kinetics in processes of nucleation and growth. Trans. Am. Instit. Mining Metall. A.LM.M.E. 135, 416-458.Google Scholar
- KANTABUTRA, V. 1983. Traveling salesman cycles are not always subgraphs of Voronoi duals. Inf. Process. Lett. 16, 11-12.Google Scholar
- KEEL, J. M., AND GUTWIN, C. A. 1989. The Delaunay triangulation closely approximates the complete Euclidean graph. Springer LNCS 382, 47-56. Google Scholar
- KL~NG, T. 1966. Random fragmentation in two and three dimensions. Z. Astrophysik 64, 433-439.Google Scholar
- KmKPATRICK, D. G. 1979. Efficient computation of continuous skeletons. In Proceedings of the 20th Annual IEEE Symposium on FOCS. pp. 18-27.Google Scholar
- KmKPATRICK, D. G. 1980. A note on Delaunay and optimal triangulations. Inf Process. Lett. 10, 127-128.Google Scholar
- KmKPATRICK, D. G. 1983. Optimal search in planar subdivisions. SIAM J. Comput. 12, 28-35.Google Scholar
- KLEE, V. 1980. On the complexity of d-dimensional Voronoi diagrams. Archiv Math. 34, 75-80.Google Scholar
- KLEIN, R. 1989. Concrete and Abstract Voronoi D~agrams. Springer LNCS 400.Google Scholar
- KLEIN, R., AND WOOD, D. 1988. Voronoi diagrams based on general metrics in the plane. Springer LNCS 294, pp.281-291. Google Scholar
- KNUTH, D. 1973. The Art of Computer Programming III: Sorting and Searching. Addison- Wesley, Reading, Mass. Google Scholar
- KocH, E. 1973. Wirkungsbereichspolyeder und Wirkungsbereichsteilungen zu kubischen Gitterkomplexen mit weniger als drei Freiheitsgraden. Z. Kristallograph. 138, 196-215.Google Scholar
- KOrEC, R. J. 1963. An alternative method for the construction of Thiessen polygons. Professional Geographer 15, 24-26.Google Scholar
- KUUSKAL, J. B. 1956. On the shortest spanning subtree of a graph and the traveling salesman problem. Problem. Am. Math. Soc. 7, 48-50.Google Scholar
- LANTUEJOUL, C., AND MAISONNEUVE, F. 1984. Geodesic methods in quantitative image analysis. Pattern Recogn. 17, 177-187.Google Scholar
- LAVES, P. 1930. Ebeneneinteilung in Wirkungsbereiche. Z. Kristallograph. 76, 277-284.Google Scholar
- LAWSON, C. L. 1972. Generation of a triangular grid with applications to contour plotting. Tech. Memorandum 299, California Inst. Tech. Jet Propulsion Lab.Google Scholar
- LAWSON, C. L. 1977. Software for C1 surface interpolation. In Mathematical Software III, J. Rice Ed., Academic Press, New York.Google Scholar
- LEE, D. T. 1980. Two-dimensional Voronoi diagrams in the Lp-metric. J. ACM 27, 604-618. Google Scholar
- LEE, D. T. 1982a. On k-nearest neighbor Voronoi diagrams in the plane. IEEE Trans. Comput. C-31,478-487.Google Scholar
- LEE, D. T. 1982b. Medial axis transform of a planar shape. IEEE Trans. Patt. Anal. Mach. Intell. PAMI-4, 363-369.Google Scholar
- LEE, D. T., AND DRYSDALE, R. L. 1981. Generalization of Voronoi diagrams in the plane. SIAM J. Comput. 10, 73-87.Google Scholar
- LEE, D. T., AND LIN, A. K. 1986. Generalized Delaunay triangulation for planar graphs. Discrete Comput. Geom. 1,201-217.Google Scholar
- LEE, D. T., AND PREPARATA, F. P. 1984. Computational geometry--A survey. IEEE Trans. Cornput. C.33, 12, 1072-1101.Google Scholar
- LEE, D. T., AND SCHACHTER, B. J. 1980. Two algorithms for constructing a Delaunay triangulation. Int. J. Comput. Inf. Sci. 9,219-242.Google Scholar
- LEE, D. T., AND WONG, C. K. 1980. Voronoi diagrams in the Ll(L~) metrics with 2- dimensional storage applications. SIAM J. Comput. 9,200-211.Google Scholar
- LEE, D. T., AND YANG, C. C. 1979. Location of multiple points in a planar subdivision. Inf. Process. Lett. 9, 190-193.Google Scholar
- LEVEN, D., AND SnARra, M. 1986. Intersection and proximity problems and Voronoi diagrams. Adv. Robotics 1, 187-228.Google Scholar
- LEwd, D., AND SHAem, M. 1987. Planning a purely translational motion of a convex robot in two-dimensional space using Voronoi diagrams. Discrete Comput. Geom. 2, 9 31.Google Scholar
- LINGAS, A. 1986a. The greedy and Delaunay triangulations are not bad in the average case. Inf. Process. Lett. 22, 25-31. Google Scholar
- LINGAS, A. 1986b. A fast algorithm for the generalized Delauuay triangulation. Manuscript, Univ. of LinkSping, Sweden.Google Scholar
- LINGAS, A. 1989. Voronoi diagrams with barriers and the shortest diagonal problem. Inf. Process. Lett. 32, 191-198. Google Scholar
- LINHART, J. 1981. Die Beleuchtung yon Kugeln. Geom. Dedicata 10, 145-154.Google Scholar
- LITTLE, D. V. 1974. A third note on recent research in geometric probability. Adv. Appl. Probab. 6, 103-130.Google Scholar
- LOEB, A. L. 1970. A systematic survey of cubic crystal structures. J. Solid State Chem. I, 237-267.Google Scholar
- MANACHER, G. K., AND ZOBRIST, A. L. 1979. Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation. Inf. Process. Lett. 9, 31-34.Google Scholar
- MATULA, D. W., AND SOKAL, R. R. 1980. Properties of Gabriel graphs relevant to geographic variation research and the clustering of points in the plane. Geograph. Anal. 12, 205-221.Google Scholar
- MATZKE, E. B., AND NESTLER, J. 1946. Volumeshape relationships in variant foams. Am. J. Botanics 33, 130-144.Google Scholar
- MAUS, A. 1884. Delaunay triangulation and the convex hull of n points in expected linear time. BIT 24, 151-163.Google Scholar
- MAXWELL, J. C. 1864. On reciprocal diagrams and diagrams of forces. Phil. Mag. 4, 27, 250-261.Google Scholar
- McLAIN, D. H. 1976. Two dimensional interpolation from random data. Comput. J. 19, 178-181.Google Scholar
- MEGIDDO, N. 1983. Linear time algorithms for linear programming in R3 and related problems. SlAM J. Comput. 12, 759-776.Google Scholar
- MEHLHORN, K., O'DUNLAING, C., AND MEISER, S. 1990. On the construction of abstract Voronoi diagrams. Springer LNCS 415, 227-239. Google Scholar
- MEIJERING, J. L. 1953. Interface area, edge length, and number of vertices in crystal aggregates with random nucleation. Philips Res. Rept. 8, 270-290.Google Scholar
- MILES, R. E. 1970. On the homogenous planar Poisson process. Math. Biosci. 6. 85-127.Google Scholar
- MITCHELL, J. S. B., MOUNT, D. M., AND PAPADIMITRIOU, C. H. 1987. The discrete geodesic problem. SIAM J. Comput. 16, 647-668. Google Scholar
- MOLLISON, D. 1977. Spatial contact models for ecological and epidemic spread. J. Roy. Stat. Soc. B 39,283-326.Google Scholar
- MONTANARI, U. 1968. A method for obtaining skeletons using a quasLEuclidean distance. J. ACM 15, 600-624. Google Scholar
- MORAN, P. A. P. 1966. A note on recent research in geometric probability. J. Appl. Probab. 3, 53-463.Google Scholar
- MORAN, P. A. P. 1969. A second note on recent research in geometrical probability. Adv. Appl. Probab. 1, 73-89.Google Scholar
- MOUNT, D. M. 1985. Voronoi diagrams on the surface of a polyhedron. Rep. 1496, Univ. of Maryland.Google Scholar
- MOUNT, D. M. 1986. Storing the subdivision of a polyhedral surface. In Proceedings of the 2nd Annual ACM Symposium on Computational Geometry. pp. 150-158. Google Scholar
- MOUNT, D., AND SAALFELO, A. 1988. Globallyequiangular triangulation of co-circular points in O(n log n) time. In Proceedings of the 4th Annual ACM Symposium on Computational Geometry. pp. 143-152. Google Scholar
- MUDER, D. J. 1988a. How big is an n-sided Voronoi polygon? Manuscript, MITRE Corp., Bedford, Mass.Google Scholar
- MUDER, D. J. 1988b. Putting the best face on a Voronoi polyhedron. Proc. London Math. Soc. 56, 329-348.Google Scholar
- MULMULEY, K. 1991. On levels in arrangements and Voronoi diagrams. Discrete Comput. Geom. In press. Google Scholar
- MURTADH, F. 1983. A survey of recent advances in hierarchical clustering algorithms. Computer J. 26, 354-359.Google Scholar
- NEWMAN, C. M., RINOTT, Y., AND TVE~SKY, A. 1983. Nearest neighbor and Voronoi regions in certain point processes. Adv. Appl. Probab. 15, 726-751.Google Scholar
- NIGGLI, R. 1927. Die topologische Strukturanalyse. Z. KristaUograph. 65, 391-415.Google Scholar
- NOWACKI, W. 1933. Der Begriff 'Voronoischer Bereich'. Z. Kristallograph. 85, 331-332.Google Scholar
- NOWACKI, W. 1976. Uber allgemeine Eigenschaften von Wirkungsbereichen. Z. KristaUograph. 143, 360-368.Google Scholar
- O'DUNLAING, C., AND YAP, C. K. 1985. A "retraction'' method for planning the motion of a disc. J. Algorithms 6, 104-111.Google Scholar
- O'DUNLAING, C., SHARIR, M., AND YAP, C. K. 1986. Generalized Voronoi diagrams for moving a ladder: I. Topological analysis. Comm. Pure Appl. Math. 39,423-483.Google Scholar
- O'DUNLAING, C., SHARm, M., AND YAP, C. K. 1987. Generalized Voronoi diagrams for moving a ladder: II. Efficient construction of the diagram. Algorithmica 2, 27-59.Google Scholar
- OHYA, T., IRI, M., AND MUROTA, K. 1984a. A fast Voronoi diagram algorithm with quaternary tree bucketing. Inf. Process. Lett. 18, 227-231. Google Scholar
- OHYA, T., IRI, M., AND MUROTA, K. 1984b. Improvements of the incremental methods for the Voronoi diagram with computational comparison of various algorithms. J. Operations Res. Soc. Japan 27, 306-337.Google Scholar
- OKABE, A., YOSHIKAWA, T., FUJII, A., AND OIKAWA, K. 1988. The statistical analysis of a distribution of active points in relation to surface-like elements. Environ. Plan. A 20, 609-620.Google Scholar
- OVERMARS, M. 1981. Dynamization of order decomposable set problems. J. Algorithms 2, 245-260.Google Scholar
- PACH, J., AND SHARIR, M. 1989. The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates. Discrete Comput. Geom. 4,291-310.Google Scholar
- PAPADTMITRIOU, C. H. 1977. The Euclidean traveling salesman problem is NP-complete. Theor. Comp. Sci. 4,237-244.Google Scholar
- PASCHINGER, I. 1982. Konvexe Polytope und Dirichletsche Zellenkomplexe. Ph.D. Dissertation, Inst. f, Math., Univ. Salzburg, Austria.Google Scholar
- 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.Google Scholar
- PRErARATA, F. P. 1977. Steps into computational geometry. Rep. R-760, Coordinated Science Lab., Univ. of Illinois, Urbana, Ill., pp, 23-24.Google Scholar
- PRErARATA, F. P., AND HONG, S. J. 1977. Convex hulls of finite sets of points in two and three dimensions. Commun. ACM 20, 87-93, Google Scholar
- PREPARATA, F. P., AND SHAMOS, M. I. 1985. Computational Geometry: An Introduction. Springer, New York. Google Scholar
- PRIM, R. C. 1957. Shortest connection networks and some generalizations Bell Syst. Tech. J. 36, 1389-1401.Google Scholar
- RAJAN, V. T. 1991. Optimality of the Delaunay triangulation in Ra. In Proceedings of the 7th Annual ACM Symposium on Computational Geometry, pp. 357-372. Google Scholar
- RHYNSBURGER, D. 1973. Analytical delineation of Thiessen polygons. Geograph. Anal. 5, 133-144.Google Scholar
- RmrA, S. 1990. Minimal roughness property of the Delaunay triangulation. Comput. Aided Geom. Design 7, 489-497. Google Scholar
- ROGERS, C. A. 1964. Packing and Covering. Cambridge University Press, London, New York.Google Scholar
- ROHNERT, H. 1988. Moving discs between polygons. Springer LNCS 317, 502-515. Google Scholar
- 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.Google Scholar
- ROSENKRANTZ, D. J., STEARNS, R. E., AND LEWm, P. M. 1977. An analysis of several heuristics for the traveling salesman problem. SIAM J. Comput. 6, 563-581.Google Scholar
- ROWAT, P. F. 1979. Representing spatial experience and solving spatial problems in a simulated robot environment. Ph.D. dissertation, Univ. of British Columbia, Canada. Google Scholar
- SAI<AMOTO, M., AND TAKAGI, M. 1988. Patterns of weighted Voronoi tessellations. Sct. Form 3, 103-111.Google Scholar
- SCH()NFLIES, A. 1891. Kristallsysteme und Kirstallstruktur. Teubner, Leipzig.Google Scholar
- SCHWARTZ, J., AND YAP, C. K. 1986. Advances in Robotics. Lawrence Erlbaum Associates, Hillside, N.J.Google Scholar
- SCHWARZKOPF, O. 1989. Parallel computation of discrete Voronoi diagrams. Springer LNCS 349, 193-204. Google Scholar
- SEIDEL, R. 1981. A convex hull algorithm optimal for point sets in even dimensions. Rep. 81-14, Univ. of Britmh Columbia, Vancouver, Canada. Google Scholar
- SEIDEL, R. 1982 The complexity of Voronoi diagrams in higher dimensions. In Proceedings of the 20th Annual Allerton Conference on CCC. pp. 94-95.Google Scholar
- SEIDEL, R. 1985 A method for proving lower bounds for certain geometric problems. In Computational Geometry, G. T. Toussaint Ed. pp. 319-334.Google Scholar
- SEIDEL, R. 1986. Constructing higher-dimensional convex hulls at logarithmic cost per face. In Proceedings of the 18th Annual ACM Symposium on STOC. pp. 404-413. Google Scholar
- SEmEL, R. 1987. On the number of faces in higher-dimensional Voronoi diagrams. In Proceedings of the 3rd Annual Symposium on Computational Geometry. pp. 181-185. Google Scholar
- SEIDEL, R. 1988. Constrained Delaunay triangulations and Voronoi diagrams with obstacles. In Rep. 260, IIG-TU Graz, Austria, pp. 178-191.Google Scholar
- SHAMOS, M. I. 1975. Geometric complexity. In Proceedings of the 7th Annual ACM Symposium on STOC. pp. 224-233. Google Scholar
- SRAMOS, M. I. 1978. Computational geometry. Ph.D. dissertation, Yale Univ., New Haven, Conn. Google Scholar
- SR^MOS, M. I., AND HOEY, D. 1975. Closest-point problems. In Proceedings of the 16th Annual IEEE Symposium on FOCS pp. 151-162.Google Scholar
- SHARm, M. 1985. Intersection and closest-pair problems for a set of planar discs. SIAM J. Comput. 14,448-468.Google Scholar
- SmsoN, R. 1977. Locally equiangular triangulations. Comput. J. 21,243-245.Google Scholar
- SmsoN, R. 1979. The Dirichlet tessellation as an aid in data analysis. Scandinavian J. Stat. 7, 14-20.Google Scholar
- SmsoN, R. 1980. A vector identity for the Dlrichlet tessellation. Math. Proc. Camb. Phil. Soc. 87, 151-155.Google Scholar
- SIFRONY, S., AND SHARIR, M. 1986. A new efficient motion-planning algorithm for a rod in polygonal space. In Proceedings of the 2nd Annual ACM Symposium on Computational Geometry. pp. 178-186. Google Scholar
- SMITH, C. S. 1954. The shape of things. Sci. Am. 58-64.Google Scholar
- SNYDEe, D. E. 1962. Urban places in Uruguay and the concept of a hierarchy. Festschrift: C. F. Jones. Northwestern University Studies in Geography 6, 29-46.Google Scholar
- STIFTER, S. 1989. An axiomatic approach to Voronoi diagrams in 3D. Manuscript, RISC, Univ. of Linz, Austria.Google Scholar
- SUGISARA, K., AND IRI, M. 1988. Geometric algorithms in finite-precision arithmetic. Research Memorandum RMI 88-10, Faculty of Engineering, Univ. of Tokyo, Japan.Google Scholar
- SuPowiT, K. J. 1983. The relative neighborhood graph, with an application to minimum spanning trees. J. ACM 30,428-448. Google Scholar
- SUZUKI, A., AND IRL M. 1986. Approximation of a tessellation of the plane by a Voronoi diagram. J. Operations Res. Soc. Japan 29, 69-96.Google Scholar
- TANEMURA, M., OGAWA, T., AND OGITA, N. 1983. A new algorithm for three-dimensional Voronoi tessellation. J. Comput. Phys. 51,191-207.Google Scholar
- T~SKI, A. 1951. A decision method for elementary algebra and geometry. Univ. of California Press, Berkeley, Calif.Google Scholar
- THmSSEN, A. H. 1911. Precipitation average for large area. Monthly Weather Rev. 39, 1082-1084.Google Scholar
- TOKUYAMA, T. 1988. Deformation of merged Voronoi diagrams with translation. Rep. TR- 88-0049, IBM Tokyo Research Lab.Google Scholar
- TOUSSA~NT, G. T. 1980. The relative neighborhood graph of a finite planar set. Pattern Recogn. 12, 261-268.Google Scholar
- 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.Google Scholar
- TUOMIN~N, O. 1949. Das EinfiuBgebeit der Stadt Turku ins System der Einfiuflgebiete SW--Finnlands. Fennia 71-5, 1-138.Google Scholar
- URQUHART, R. 1980. A note on the computation of subgraphs of the Delaunay triangulation. Rep., Univ. of Glasgow, U.K.Google Scholar
- V~OYA, P. M. 1988a. Minimum spanning trees in k-dimensional space. SIAM J. Comput. 17, 572-582. Google Scholar
- VAIDYA, P. M. 1988b. Geometry helps in matching. In Proceedings of the 20th Annual ACM Symposium on STOC. pp. 422-425. Google Scholar
- VORONOI, M. G. 1908. Nouvelles applications des parametres continus a la theorie des formes quadratiques. J. Reine Angew. Math. 134, 198-287.Google Scholar
- WANG, C. A., AND SCHUBERT, L. 1987. An optimal algorithm for constructing the Delaunay triangulation of a set of line segments. In Proceedings of the 3rd Annual ACM Symposium on Computational Geometry. pp. 223-232. Google Scholar
- WATSON, D. F. 1981. Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes. Comput. J. 24, 167-172.Google Scholar
- WEAmE, D., ANn RWmR, N. 1984. Soap, cells, and statistics--random patterns in two dimensions. Contemp. Phys. 25, 59-99.Google Scholar
- WmTELEY, W. 1979. Realizability of polyhedra. Structural Topol. 1, 46-58.Google Scholar
- WmMEIER, P., Wu, Y. F., AND WONG, C. K. 1987. On some distance problems in fixed orientations. SIAM J. Comput. 16, 728-746. Google Scholar
- WIGNER, E., AND SEITZ, F. 1933. On the constitution of metallic sodium. Phys. Rev. 43, 804-810.Google Scholar
- WmLIAMS, R. E. 1968. Space-filling polyhedron: Its relation to aggregates of soap bubbles, plant cells, and metal crystalites. Science 161, 276-277.Google Scholar
- YAO, A. C. 1975. An O(E log log V) algorithm for finding minimum spanning trees. Inf. Process. Lett. 4, 21-23.Google Scholar
- YAO, A. C. 1982. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM J. Comput. 11,721-736.Google Scholar
- YAP, C. K. 1987. An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments. Discrete Comput. Geom. 2, 365-393.Google Scholar
Index Terms
- Voronoi diagrams—a survey of a fundamental geometric data structure
Recommendations
Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes
SoCG '11: Proceedings of the twenty-seventh annual symposium on Computational geometryGiven a set Σ of spheres in Ed, with d≥3 and d odd, having a fixed number of m distinct radii ρ1,ρ2,...,ρm, we show that the worst-case combinatorial complexity of the convex hull CHd(Σ) of Σ is Θ(Σ{1≤i≠j≤m}ninj⌊ d/2 ⌋), where ni is the number of ...
Convex hulls of spheres and convex hulls of disjoint convex polytopes
Given a set @S of spheres in E^d, with d>=3 and d odd, having a constant number of m distinct radii @r"1,@r"2,...,@r"m, we show that the worst-case combinatorial complexity of the convex hull of @S is @Q(@__ __"1"=<"i"<>"j"=<"mn"in"j^@__ __^d^2^@__ __), ...
A Bichromatic Incidence Bound and an Application
We prove a new, tight upper bound on the number of incidences between points and hyperplanes in Euclidean d-space. Given n points, of which k are colored red, there are Od(m2/3k2/3n(dź2)/3+kndź2+m) incidences between the k red points and m hyperplanes ...
Comments