% Geometry papers already entered in CS445 bibliography
% GeoPapers.bravo of December 18, 1982 12:29 AM - Leo/Jorge
==>> JALG ------ from minf (= 1980) to present
Lipski, W., Jr., and Preparata, F. P., " Finding the contour of a union of
iso-oriented rectangles", J. Alg. 1, 235-246 (1980).
Does it in time O(m lg m + p lg (2m↑2/p)), where m = # of rectangles, p
= # of edges in the contour.
Lipski, W., Jr., and Preparata, F. P., " Segments, rectangles, contours", J. Alg. 2,
63-76 (1981).
For a collection of n vertical and horizontal line segments, the authors
compute several kinds of contours based on a common structure.
Gindy, H. El, and Avis, D., "A linear-time algorithm for computing the visibility
polygon from a point", J. Alg. 2, 186-197 (1981).
Perhaps to be presented together with Graham-Yao.
van Leeuwen, J., and Wood, D., "The measure problem for rectangular ranges in
d-space", J. Alg. 2, 282-300 (1981).
Does in time O(n↑(d-1)) and quadratic storage for d > 2.
Lee, D. T., and Wong, C. K., "Finding intersections of rectangles by range
search", J. Alg. 2, 337-347 (1981).
Still uses O(n lg n) storage for d = 2.
Vaishnavi, V. K., Wood, D., "Rectilinear line segment intersection, layered
segment trees, and dynamization", J. Alg. 3, 160-176 (1982).
Learn about layered segment trees.
Lee, D. T., and Preparata, F. P., "An improved algorithm for the rectangle
enclosure problem", J. Alg. 3, 218-224 (1982)
==>> JACM ------ from 1976 to present
Bentley, J. L., Kung, H. T., Schkolnick, M., and Thompson, C. D., "On the
average number of maxima in a set of vectors and applications", JACM 25,
536-543 (1978).
Derives said average (= O((lg n)↑(d-1))) and related algorithm.
Hwang, F. K., " An O(n log n) algorithm for rectilinear minimal spanning trees",
JACM 26, 177-182 (1979).
L1 Voronoi and mst.
Cohen, J., and Hickey, T., "Two algorithms for determining volumes of convex
polyhedra", JACM 26, 401-414 (1979).
Marginal.
Lee, D. T., "Two-dimensional Voronoi diagrams in the Lp-Metric", JACM 27,
604-618 (1980).
Good.
Yao, A. C., "A lower bound to finding convex hulls", JACM 28, 780-787 (1981).
Only worthwhile lower bound around.
==>> SICOMP ------ from 1975 to present
Dobkin, D., and Lipton, R., J., "Multidimensional searching problems", SICOMP
5, 181-186 (1976).
Binary search generalized.
Lee, D. T., and Preparata, F. P., "Location of a point in a planar subdivision and
its applications", SICOMP 6, 594-606 (1977).
A classic.
Preparata, F. P., "A note on locating a set of points in a planar subdivision",
SICOMP 8, 542-545 (1979).
The benefits of batching.
Lee, D. T., and Wong, C. K., "Voronoi diagrams in L1 (Linf) metrics with
2-dimensional storage applications", SICOMP 9, 200-211 (1980).
More Voronoi.
Yao, A. C., and Rivest, R. L., "On the polyhedral decision problem", SICOMP 9,
343-347 (1980).
The complexity of polytope inclusion in terms of faces.
Lipton, R. J., and Tarjan, R. E., "Applications of a planar separator theorem",
SICOMP 9, 615-627 (1980).
Post office.
Lee, D. T., and Drysdale, R. L., III, "Generalization of Voronoi diagrams in the
plane", SICOMP 10, 73-87 (1981).
Voronoi of line segments.
Preparata, F. P., "A new approach to planar point location", SICOMP 10, 473-482
(1981).
Segment tree use.
Papadimitriou, C. H., "Worst-case and probabilistic analysis of a geometric
location problem", SICOMP 10, 542-557 (1981).
Selecting reps in L1.
Burton, R. P., and Smith D. R., "A hidden-line algorithm for hyperspace",
SICOMP 11, 71-80 (1982).
Fiction.
Willard, D. E., "Polygon retrieval", SICOMP 11, 149-165 (1982).
Good.
Comer, D., and O'Donnell, M. J., "Geometric problems with application to
hashing", SICOMP 11, 217-226 (1982).
Min span of n points, etc.
Yao, A. C., "On constructing minimum spanning trees in k-dimesnional spaces
and related problems", SICOMP 11, 721-736 (1982).
Wonderful.
==>> IPL ------ from minf (= 1972) to present
Edelsbrunner, H., and Overmars, M. H., "On the equivalence of some rectangle
problems", IPL 14, 124-127 (1982).
Equivalence of rectangle to dominance problems.
Schwartz, J. T., "Finding the minimum distance between two convex polygons",
IPL 13, 168-170 (1981).
In time O(lg↑2 n).
Edelsbrunner, H., Maurer, H. A., and Kirkpatrick, D. G., "Polygonal intersection
searching", IPL 14, 74-79 (1982).
Given lots of starage, you can do everything fast.
Jarvis, R. A., "On the identification of the convex hull of a finite set of points in
the plane", IPL 2, 18-21 (1973).
A classic.
Graham, R. L., "An efficient algorithm for determining the convex hull of a
finite planar set", IPL 1, 132-133 (1972).
An even greater classic.
Rohlf, F. J., "A probabilistic minimum spanning tree algorithm", IPL 7, 44-48
(1978).
Uses ever coarsening grids for delta-neighbors.
Jaromczyk, J. W., "Linear decision trees are too weak for convex hull problem",
IPL 12, 138-141 (1981).
Cover in class.
Bentley, J. L., and Stanat, D. F., "Analysis of range searches in quad trees", IPL
6, 170-173 (1975).
And comparison with empirical data.
Overmars, M. H., and van Leeuwen, J., "Worst-case optimal insertion and
deletion methods for decomposable searching problems", IPL 12, 168-173 (1981).
Applications to dynamic range queries and nearest neighbor searching.
Akl, S. G., "Comments on: G. Manacher, An application of pattern matching to a
problem in geometrical complexity", IPL 7, 86 (1978).
OK.
Bykat, A., "Convex hull of a finite set of points in two dimensions", IPL 7,
296-298 (1978).
Floyd-like idea - shown to be O(n↑2) by Fournier.
Fortune, S., and Hopcroft, J., "A note on Rabin's nearest-neighbor algorithm", IPL
8, 20-23 (1979).
Unrandomized, in time O(n lg lg n).
Akl, S. G., "Two remarks on a convex hull algorithm", IPL 8, 108-109 (1979).
Bug found and fixed.
Bentley, J. L., "Decomposable searching problems", IPL 8, 244-251 (1979).
Fundamental methodology.
Lee, D. T., and Yang, C. C., "Location of multiple points in a planar subdivision",
IPL 9, 190-193 (1979).
Trivial.
Andrew, A. M., "Another efficient algorithm for convex hulls in two
dimensions", IPL 9, 216-219 (1979).
Sort in x.
van Emde Boas, P., "On the Omega(n log n) lower bound for convex hull and
maximal vector determination", IPL 10, 132-136 (1980).
Perhaps another useless variation.
None, "Corrigendum on convex hull algorithms", IPL 10, 168 (1980).
None.
Avis, D., "Comments on a lower bound for convex hull determination", IPL 11,
126 (1980).
Linear tests don't suffice.
Williams, M. H., "Cubic map configurations", IPL 11, 180-185 (1980).
Oddball.
Bykat, A., "On polygon similarity", IPL 9, 23-25 (1979).
Tests affine equivalence in O(n).
Manacher, A. L., and Zobrist, A. L., "Neither the greedy nor the Delaunay
triangulation of a planar point set approximates the optimal triangulation", IPL 9,
31-34 (1979).
Unbounded ratios.
Fournier, A., and Kedem, Z., "Comments on the all nearest-neighbohr problem
for convex polygons", IPL 9, 105-107 (1979).
Comments on Lee and Preparata, and Yang and Lee.
D{/}evai, F., and Szendr{/}enyi, T., "Comments on convex hull of a finite point
set in two dimensions", IPL 9, 141-142 (1979).
Bykat is wrong.
McCallum, D., and Avis, D., "A linear algorithm for finding the convex hull of
a simple polygon", IPL 9, 201-206 (1979).
Possibly erroneous.
Akl, S. G., "Addendum to "An improved algorithm to check for polygon
similarity"", IPL 8, 157-158 (1979).
Bug found and corrected.
Yang, C. C., and Lee, D. T., "A note on the all nearest-neighbor problem for
convex polygons", IPL 8, 193-194 (1979).
Instead of diameter, use four extremal vertices in x and y.
Fournier, A., "Comments on convex hull of a finite set of points in two
dimensions", IPL 8, 193-194 (1979).
Bykat is wrong.
Silva-Filho, Y. V., "Average case analysis of region search in balanced k-d
trees", IPL 8, 219-223 (1979).
More rigorous analysis to derive O(sqrt(n)) bound.
Yuval, G., "Finding near-neighbours in k-dimensional space", IPL 3, 113-114
(1975).
Grid used as buckets.
Kirkpatrick, D. G., "A note on Delaunay and optimal triangulations", IPL 10,
127-128 (1980).
Delaunay is even worse than Manacher and Zobrist showed.
Overmars, M. H., and van Leeuwen, J., "Further comments on Bykat's convex
hull algorithm", IPL 10, 209-212 (1980).
Bykat = Eddy, proof of linearity for uniform distribution.
Dyer, C. R., "A fast parallel algorithm for the closest pair problem", IPL 11, 49-52
(1980).
Linear time, with quadratic processors.
Devroye, L., "A note on finding convex hulls via maximal vectors", IPL 11, 53-56
(1980).
Distribution on number of maximal vectors.
Akl, S. G., and Toussaint, T., "An improved algorithm to check for polygon
similarity", IPL 7, 127-128 (1978).
Improvements on Manacher.
Bentley, J. L., and Shamos, M. I., "Divide and conquer for linear expected time",
IPL 7, 87-91 (1978).
By Renyi, merge step is sublinear.
Akl, S. G., and Toussaint, G. T., "A fast convex hull algorithm", IPL 7, 219-222
(1978).
Eddy + x-sort.
Lee, D. T., and Preparata, F. P., "The all nearest-neighbor problem for convex
polygons", IPL 7, 189-192 (1978).
In linear time.
Garey, M. R., Johnson, D. S., Preparata, F. P., and Tarjan, R. E., "Triangulating a
simple polygon", IPL 7, 175-179 (1978).
A classic.
Fowler, R. J., Paterson, M. S., and Tanimoto, S. L., "Optimal packing and
covering in the plane are NP-complete", IPL 12, 133-137 (1981).
Some geometric NP-completeness results.
Raghavan, V. V., and Yu, C. T., "A note on a multidimensional searching
problem", IPL 6, 133-135 (1977).
Unclear.
Bentley, J. L., Stanat, D. F., and Williams, E. H., Jr., "The complexity of finding
fixed-radius near neighbors", IPL 6, 209-212 (1977).
Trivial.
Yuval, G., "Finding nearest neighbours", IPL 5, 63-65 (1976).
Buckets.
Edelsbrunner, H., and Maurer, H. A., "On the intersection of orthogonal objects",
IPL 13, 177-181 (1981).
Segment tree use.
Silva Filho, Y. V., "Optimal choice of discriminators in a balanced k-d binary
search tree", IPL 13, 67-70 (1981).
OK.
Preparata, F. P., and Supowit, K. J., "Testing a simple polygon for monotonicity",
IPL 12, 161-164 (1981).
In linear time.
==>> CACM ------ from 1976 to present
Clark, J. H., "Designing surfaces in 3-D", CACM 19, 454-460 (1976).
Graphics system.
Preparata, F. P., and Hong, S. J., "Convex hulls of finite sets of points in two and
three dimensions", CACM 20, 87-93 (1977).
Important classic.
Fredman, M. L., and Weide, B., "On the complexity of computing the measure of
\Union[ai, bi]", CACM 21, 540-544 (1978).
Nice lower bound arguments.
Boyse, J. W., "Interference detection among solids and surfaces", CACM 22, 3-9
(1979).
Shallow - engineering.
Shapira, R., and Freman, H., "The cyclic order property of vertices as an aid in
scene analysis", CACM 22, 3-9 (1979).
Which diagrams correspond to solids?
Preparata, F. P., "An optimal real time algorithm for planar convex hulls", CACM
22, 402-405 (1979).
Nice.
Lozano-P{\}erez, T., and Wesley, M. A., "An algorithm for planning collision
free paths among polyhedral obstacles", CACM 22, 560-570 (1979).
Interesting high-level ideas.
Samet, H., "Deletion in two-dimesnional quad trees", CACM 23, 703-710 (1980).
Reasonable analysis.
Ballard, D. H., "Strip trees: A hierarchical representation for curves", CACM 24,
310-321 (1981).
Hierarchical tree representation for curves, closed under boolean
operations.
Bentley, J. L., and Faust, M. G., "Approximate algorithms for convex hulls",
CACM 25, 64-68 (1982).
Approximate algorithms, in linear time.
Suzuki, N., "Analysis of pointer rotation", CACM 25, 330-335 (1982).
Approximate algorithms, in linear time.
Lee, Y. T., and Requicha, A. A. G., "Algorithms for computing the volume and
other integral properties of solids. I. Known methods and open issues. II. A family
of algorithms based on representation conversion and cellular approximation",
CACM 25, 635-650 (1982).
Oddball.
Nievergelt, J., and Preparata, F. P., "Plane-sweep algorithms for intersecting
geometric figures", CACM 25, 739-747 (1982).
Good, Stolfi can do better.