Item


Approximating generalized distance functions on weighted triangulated surfaces with applications

Given P, a simple connected, possibly non-convex, polyhedral surface composed of positively weighted triangular faces, we consider paths from generalized sources (points, segments, polygonal chains or polygonal regions) to points on P that stay on P and avoid obstacles (segments, polygonal chains or polygonal regions). The distance function defined by a generalized source is a function that assigns to each point of P the cost of the shortest path from the source to the point. In this paper we present an algorithm for computing approximate generalized distance functions. We also provide an algorithm that computes a discrete representation of the approximate distance function and, as applications, algorithms for computing discrete order-k Voronoi diagrams and for approximately solving facility location problems. Finally, we present experimental results obtained with our implementation of the provided algorithms

This work was partially supported by the Spanish Ministerio de Ciencia e Innovacion under grant TIN2010-20590-C02-02

Elsevier

Manager: Ministerio de Ciencia e Innovación (Espanya)
Author: Fort, Marta
Sellarès i Chiva, Joan Antoni
Abstract: Given P, a simple connected, possibly non-convex, polyhedral surface composed of positively weighted triangular faces, we consider paths from generalized sources (points, segments, polygonal chains or polygonal regions) to points on P that stay on P and avoid obstacles (segments, polygonal chains or polygonal regions). The distance function defined by a generalized source is a function that assigns to each point of P the cost of the shortest path from the source to the point. In this paper we present an algorithm for computing approximate generalized distance functions. We also provide an algorithm that computes a discrete representation of the approximate distance function and, as applications, algorithms for computing discrete order-k Voronoi diagrams and for approximately solving facility location problems. Finally, we present experimental results obtained with our implementation of the provided algorithms
This work was partially supported by the Spanish Ministerio de Ciencia e Innovacion under grant TIN2010-20590-C02-02
Format: application/pdf
Document access: http://hdl.handle.net/10256/11987
Language: eng
Publisher: Elsevier
Collection: info:eu-repo/semantics/altIdentifier/doi/10.1016/j.cam.2012.03.028
info:eu-repo/semantics/altIdentifier/issn/0377-0427
info:eu-repo/grantAgreement/MICINN//TIN2010-20590-C02-02/ES/AVANCES EN REALIDAD VIRTUAL PARA APLICACIONES PUNTERAS-UDG/
Rights: Tots els drets reservats
Subject: Polígons
Polygons
Algorismes computacionals
Computer algorithms
Title: Approximating generalized distance functions on weighted triangulated surfaces with applications
Type: info:eu-repo/semantics/article
Repository: DUGiDocs

Subjects

Authors


Warning: Unknown: write failed: No space left on device (28) in Unknown on line 0

Warning: Unknown: Failed to write session data (files). Please verify that the current setting of session.save_path is correct (/var/lib/php5) in Unknown on line 0