The weighted region problem
From MaRDI portal
Publication:4302828
DOI10.1145/102782.102784zbMath0799.68150OpenAlexW1989723858MaRDI QIDQ4302828
Joseph S. B. Mitchell, Christos H. Papadimitriou
Publication date: 13 November 1994
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://hdl.handle.net/1813/8768
nonlinear programmingshortest pathsVoronoi diagramsSnell's Law of Refractionweighted planar polygonal subdivision
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Paths and cycles (05C38) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items (57)
SHORTEST DESCENDING PATHS: TOWARDS AN EXACT ALGORITHM ⋮ Approximating Nearest Neighbor Distances ⋮ An ε — Approximation algorithm for weighted shortest paths on polyhedral surfaces ⋮ An \(\Omega (n^d)\) lower bound on the number of cell crossings for weighted shortest paths in \(d\)-dimensional polyhedral structures ⋮ Unnamed Item ⋮ Navigating Weighted Regions with Scattered Skinny Tetrahedra ⋮ On approximating shortest paths in weighted triangular tessellations ⋮ A new mixed-integer linear programming model for rescue path planning in uncertain adversarial environment ⋮ An approximation algorithm for computing shortest paths in weighted 3-d domains ⋮ Approximating shortest path for the skew lines problem in time doubly logarithmic in 1/epsilon ⋮ Fastest-path planning for direction-dependent speed functions ⋮ Shortest monotone descent path problem in polyhedral terrain ⋮ Algorithms for approximate shortest path queries on weighted polyhedral surfaces ⋮ Shortest paths in the plane with obstacle violations ⋮ Fast query structures in anisotropic media ⋮ A survey of motion planning algorithms from the perspective of autonomous UAV guidance ⋮ Shortest Journeys in Directed Temporal Graphs ⋮ Line Facility Location in Weighted Regions ⋮ Path planning in a weighted planar subdivision under the Manhattan metric ⋮ Approximating generalized distance functions on weighted triangulated surfaces with applications ⋮ Gate points in continuous location between regions with different \(\ell _{p}\) norms ⋮ CONSTRUCTING THE CITY VORONOI DIAGRAM FASTER ⋮ A survey of geodesic paths on 3D surfaces ⋮ Pasting gauges. I: Shortest paths across a hyperplane ⋮ On the complexity of time-dependent shortest paths ⋮ Fixed gate point location problems ⋮ \(L_ 1\) shortest paths among polygonal obstacles in the plane ⋮ GENERALIZED WATCHMAN ROUTE PROBLEM WITH DISCRETE VIEW COST ⋮ An Experimental Study of Weighted k-Link Shortest Path Algorithms ⋮ Single-facility location problems in two regions with \(\ell_{1}\)- and \(\ell_q\)-norms separated by a straight line ⋮ APPROXIMATE SHORTEST HOMOTOPIC PATHS IN WEIGHTED REGIONS ⋮ A catalog of Hanan grid problems ⋮ Finding rectilinear least cost paths in the presence of convex polygonal congested regions ⋮ Quickest path queries on transportation network ⋮ A note on the unsolvability of the weighted region shortest path problem ⋮ FRÉCHET DISTANCE PROBLEMS IN WEIGHTED REGIONS ⋮ Line facility location in weighted regions ⋮ Approximation algorithms for shortest descending paths in terrains ⋮ On approximating shortest paths in weighted triangular tessellations ⋮ Shortest Gently Descending Paths ⋮ SKEW VORONOI DIAGRAMS ⋮ Pursuit evasion on polyhedral surfaces ⋮ Region-restricted clustering for geographic data mining ⋮ Path refinement in weighted regions ⋮ Unnamed Item ⋮ MINIMUM SEPARATION IN WEIGHTED SUBDIVISIONS ⋮ Density-Based Clustering Based on Topological Properties of the Data Set ⋮ Modeling Optimal Beam Treatment with Weighted Regions for Bio-medical Applications ⋮ VORONOI DIAGRAMS FOR A TRANSPORTATION NETWORK ON THE EUCLIDEAN PLANE ⋮ On p-harmonic functions, convex duality and an asymptotic formula for injection mould filling ⋮ Line Segment Facility Location in Weighted Subdivisions ⋮ Shortest descending paths through given faces ⋮ The transportation metric and related problems ⋮ Rectilinear paths among rectilinear obstacles ⋮ On discretization methods for approximating optimal paths in regions with direction-dependent costs ⋮ Geometric optimization and sums of algebraic functions ⋮ Computing Shortest Paths in the Plane with Removable Obstacles
This page was built for publication: The weighted region problem
