Solving Geometric Optimization Problems using Graphics Hardware
| dc.contributor.author | Denny, Markus | en_US |
| dc.date.accessioned | 2015-02-16T08:01:12Z | |
| dc.date.available | 2015-02-16T08:01:12Z | |
| dc.date.issued | 2003 | en_US |
| dc.description.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 | en_US |
| dc.description.number | 3 | en_US |
| dc.description.seriesinformation | Computer Graphics Forum | en_US |
| dc.description.volume | 22 | en_US |
| dc.identifier.doi | 10.1111/1467-8659.00692 | en_US |
| dc.identifier.issn | 1467-8659 | en_US |
| dc.identifier.pages | 441-451 | en_US |
| dc.identifier.uri | https://doi.org/10.1111/1467-8659.00692 | en_US |
| dc.publisher | Blackwell Publishers, Inc and the Eurographics Association | en_US |
| dc.title | Solving Geometric Optimization Problems using Graphics Hardware | en_US |