Time Convex Hull with a Highway
Authors:
- 1 July 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 240-250
Abstract
We consider the problem of computing the time convex hull of a set of points in the presence of a straight-line highway in the plane. The traveling speed in the plane is assumed to be much slower than that along the highway. The shortest time path between two arbitrary points is either the straight-line segment connecting these two points or a path that passes through the highway. The time convex hull, CHt(P), of a set P of n points is the smallest set containing P such that all the shortest time paths between any two points lie in CHt(P). In this paper we give a Theta(n log n) time algorithm for solving the time convex hull problem for a set of n points in the presence of a highway.Keywords
This publication has 8 references indexed in Scilit:
- Voronoi Diagram for services neighboring a highwayInformation Processing Letters, 2003
- SKEW VORONOI DIAGRAMSInternational Journal of Computational Geometry & Applications, 1999
- A New Approach for the Geodesic Voronoi Diagram of Points in a Simple Polygon and Other Restricted Polygonal DomainsAlgorithmica, 1998
- Lower bounds for algebraic computation trees1983
- Generalization of Voronoi Diagrams in the PlaneSIAM Journal on Computing, 1981
- Two-Dimensional Voronoi Diagrams in the
L
p
-MetricJournal of the ACM, 1980
- Finding the intersection of n half-spaces in time O(n log n)Theoretical Computer Science, 1979
- An efficient algorith for determining the convex hull of a finite planar setInformation Processing Letters, 1972