Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Computational Geometry: Theory and Applications (v.1 n.1)Sack J. Urrutia J. (ed)   Computational Geometry: Theory and Applications 11:1991. Type: Journal
Date Reviewed: Sep 1 1993
Comparative Review

In a 1989 survey talk, I predicted that two new journals devoted to computational geometry would appear within a decade. My prediction was realized in under two years, with the publication of the International Journal of Computational Geometry and Applications, edited by D. T. Lee, and Computational Geometry: Theory and Applications, the journal under review. This journal mentions “theory” in its title, while Lee’s journal does not, and one might therefore expect a slight separation between the two along the theory-applications continuum.

The first issue of this journal contains four papers ranging in scope from pure theory to practical theory.

Avis, Erdoös, and Pach

The first paper, by Avis, Erdoös, and Pach, contributes to our understanding of the difficult combinatorics of distinct distances determined by a set of points, an area initiated and extensively explored by Erdoös. Four points on a line usually determine ( 42 = 6 ) distinct distances, but four equally spaced points only determine three distinct distances. One would expect most four-element subsets of a large set to determine six distances, even if the set is highly regular. A typical result from this paper confirms and quantifies this intuition: as n tends to infinity, almost all k-element subsets of n points in the plane determine ( k2 ) distinct distances, if k is small relative to n: k = o ( n 17 ).

de Berg

The second paper, by de Berg, studies orthogonal (or rectilinear) link distance in an orthogonal polygon: the minimum number of horizontal and vertical segments in a path connecting a pair of points, in a polygon itself composed entirely of horizontal and vertical edges. His results hinge on an extension of Chazelle’s polygon-cutting theorem to the orthogonal world: an orthogonal polygon with weighted vertices can be cut in two with a horizontal or vertical chord so that the weight of each piece is at most ¾ of the total. This theorem leads (among other results) to an algorithm for computing the orthogonal link diameter in O ( n log n ) time for an orthogonal polygon of n vertices.

Overmars and Sharir

In the third paper, Overmars and Sharir show how to merge visibility maps efficiently. Visibility maps are subdivisions of a viewing window into regions within which only one object is visible, computed by object-space hidden surface removal algorithms. Merging of maps is useful, for example, in animation, where the map of the environment is fixed and a moving object map needs to be interleaved with the environment map. Perhaps more important, map merging is a step toward a truly output-size sensitive hidden surface algorithm, one dependent more on k, the size of the output visibility map, than on n, the size of the input. For example, Overmars and Sharir obtain an algorithm for hidden surface removal for a scene of n disjoint unit spheres that requires O ( ( n + k ) log 2 n ) time, considerably better than the naïve O ( n 2 ) algorithm.


The final paper in this issue, by Seidel, offers a simple and fast randomized polygon triangulation algorithm. Chazelle’s breakthrough discovery of an O ( n ) deterministic algorithm settled the theoretical issue, but practical algorithms that approach the theoretical speed achievements have remained elusive. Seidel’s algorithm is remarkably simple: insert the edges of the polygon into a simple “trapezoidation” data structure in random order, and every once in a while ( log* n times), update some information in the structure. The result is an O ( n log* n ) expected-time algorithm that avoids divide-and-conquer, complex data structures, and other implementation hurdles.

Reviewer:  Joseph O’Rourke Review #: CR115947
Comparative Review
This review compares the following items:
  • Computational Geometry: Theory and Applications (v.1 n.1):
  • Merging visibility maps:
  • Distinct distances determined by subsets of a point set in space:
  • On rectilinear link distance:
  • ASLIB Proceedings (v.43 n.2/3):
  • Bookmark and Share
      Featured Reviewer  
    Geometrical Problems And Computations (F.2.2 ... )
    Library Automation (H.3.6 )
    Counting Problems (G.2.1 ... )
    Geometric Algorithms, Languages, And Systems (I.3.5 ... )
    Hidden Line/ Surface Removal (I.3.7 ... )
    Visible Line/ Surface Algorithms (I.3.7 ... )
    Approximation (G.1.2 )
    Data Structures (E.1 )
    Would you recommend this review?
    Other reviews under "Geometrical Problems And Computations": Date
    Using field cocitation analysis to assess reciprocal and shared impact of LIS-MIS fields
    Sugimoto C., Pratt J., Hauser K.  Journal of the American Society for Information Science and Technology 59(9): 1441-1453, 2008. Type: Article
    May 1 2009
    Trends and issues in establishing interoperability among knowledge organization systems
    Zeng M., Chan L.  Journal of the American Society for Information Science and Technology 55(5): 377-395, 2004. Type: Article
    Jun 18 2004
    A view to the future of the library and information science profession: a Delphi study
    Arbib S.  Journal of the American Society for Information Science 53(5): 397-408, 2002. Type: Article
    Aug 9 2002

    E-Mail This Printer-Friendly
    Send Your Comments
    Contact Us
    Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2021 ThinkLoud, Inc.
    Terms of Use
    | Privacy Policy