The intersection searching problem for c-oriented polygons
Information Processing LettersPublished 1 February 1991
Xuehou Tan, Tomio Hirata, Yasuyoshi Inagaki
Citations11
SJR quartileQ3
SJR score0.41
SNIP0.73
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown that a c- oriented polygon intersection query can be answered in O(log n+t) time using O(n log n) space, where n is the number of c-oriented polygons, each with a bounded number of edges, and t is thenumber of reported polygons.
Abstract
In this paper, we show that the universal covering space of a surface can be used to unify previous results on computing paths in a simple polygon. We optimize a given path among obstacles in the plane under the Euclidean and link metrics and under polygonal convex distance functions. Besides revealing connections between the minimum paths under these three distance functions, the framework provided by the universal cover leads to simplified linear-time algorithms for shortest path trees, for minimum-link paths in simple polygons, and for paths restricted to c given orientations.
Keywords
Computer Science
Scaling and related techniques for geometry problems
516 Citations1984Harold N. Gabow, Jon Bentley +1 more
Three techniques in computational geometry are explored: scaling solves a problem by viewing it at increasing levels of numerical precision; activation is a restricted type of update operation, useful in sweep algorithms; the Cartesian tree is a data structure for problems involving maximums and minimums.
SIAM Journal on ComputingFiltering Search: A New Approach to Query-Answering
298 Citations1986Bernard Chazelle
This work introduces a new technique for solving problems of the following form: preprocess a set of objects so that those satisfying a given property with respect to a query object can be listed very effectively.
Information Processing LettersHalfplanar range search in linear space and O(n0.695) query time
94 Citations1986Herbert Edelsbrunner, Emo Welzl
A new data structure is described which stores S in O(n) space and allows us to answer a halfplanar range query in O (n log 2 (1+√5)−1) time in the worst case, thus improving the best result known before.
Computer Vision Graphics and Image ProcessingNew algorithms for special cases of the hidden line elimination problem
48 Citations1987Ralf Hartmut Güting, Thomas Ottmann
Three special cases of increasing difficulty and generality of the hidden line elimination problem are studied, and applying some methods from computational geometry these problems can be solved with better worst-case bounds than those of the best known algorithms for the general problem.
Information Processing LettersPolygonal intersection searching
43 Citations1982Herbert Edelsbrunner, Hermann Maurer +1 more
Discrete & Computational GeometryLinear space data structures for two types of range search
37 Citations1987Bernard Chazelle, Herbert Edelsbrunner
This paper examines thehomothetic range search problem, where a setS ofn points in the plane is to be preprocessed so that for any triangleT with sides parallel to three fixed directions the points ofS that lie inT can be computed efficiently, and looks at domination searching in three dimensions.
Information and ComputationOptimal computation of finitely oriented convex hulls
32 Citations1987Gregory J. E. Rawlins, Derick Wood
Four versions of the “convex hull” of a simple finitely oriented polygon are defined and optimal algorithms to find them are given and it is shown that testing whether an arbitrary simple polygon is (finitely oriented) convex has worst-case time and space complexity θ ( n + f ) and η ( n ), respectively.
Information Processing LettersStabbing c-oriented polygons
32 Citations1983Ralf Hartmut Güting
The notion of c-oriented objects is introduced, that is, objects whose edges are oriented in only a constant number of previously defined directions, and time-optimal algorithms for determining the stabbing numbers of points with respect to a set ofc-oriented polygons are devised.
Distance problems in computational geometry with fixed orientations
26 Citations1985Peter Widmayer, Y. F. Wu +1 more
A family of naturally induced metrics is introduced, and the subsequent generalization of geometrical concepts are introduced, which may help bridge the gap between the L1- and the L2-metrics, as those are the limiting cases for two and infinitely many regularly distributed orientations.
Information and ControlDynamic C-oriented polygonal intersection searching
23 Citations1984Ralf Hartmut Güting
It is shown that the c -oriented intersection searching problem can be solved in O (log 2 n + t ) time with O (n log n ) space and O ( n log 2 n ) preprocessing, where n is the cardinality of P and t the number of answers to a query.
Journal of AlgorithmsPoint retrieval for polygons
20 Citations1986Michael S. Paterson, Fei Yao
This work presents a solution to the following polygon retrieval problem: given a set of n points on the plane, build a data structure so that for any query polygon P the set of points lying in P can be retrieved efficiently.
Turtlegons
13 Citations1985Joseph Culberson, Gregory J. E. Rawlins
An algorithm to create simple polygons with a particular sequence of exterior angles given only the sequence of angles is presented, which proves an interesting converse of the ancient theorem that the sum of the exterior angles of a simple polygon is 2π radians.
Lecture notes in computer scienceSpatial point location and its applications
5 Citations1990Xuehou Tan, Tomio Hirata +1 more
A persistent form of binary-binary search tree is presented so that the point location problem can be solved in O(log N) query time and O(N+K) space, where N is the total number of edges and K the edge intersections in the image plane.