Solving Geometric Optimization Problems using Graphics Hardware
No Thumbnail Available
Date
2003
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Blackwell Publishers, Inc and the Eurographics Association
Abstract
We show how to use graphics hardware for tackling optimization problems arising in the field of computationalgeometry. We exemplarily discuss three problems, where combinatorial algorithms are inefficient or hard to implement.Given a set S of n point in the plane, the first two problems are to determine the smallest homotheticscaling of a star shaped polygon P enclosing S and to find the largest empty homothetic scaling of P completelycontained inside an arbitrary polygonal region. Pixel-exact solutions for both problems are computed in real-time.The third problem is a facility location problem and more difficult to solve. Given the Voronoi diagram VoD(S) ofthe n points, we try to position another point p in the plane, such that the resulting Voronoi region of p has maximalarea. As far as we know there exists no traditional solution for this problem for which we present pixel-exactsolutions.Categories and Subject Descriptors (according to ACM CCS): I.3.5 [Computer Graphics]: Geometric algorithms,languages, and systems I.3.3 [Computer Graphics]: Display algorithms
Description
@article{10.1111:1467-8659.00692,
journal = {Computer Graphics Forum},
title = {{Solving Geometric Optimization Problems using Graphics Hardware}},
author = {Denny, Markus},
year = {2003},
publisher = {Blackwell Publishers, Inc and the Eurographics Association},
ISSN = {1467-8659},
DOI = {10.1111/1467-8659.00692}
}