Optimal Geometric Partitions, Covers and K-Centers

Mugurel Ionut Andreica(mugurelionutgmail.com)
Eliana-Dina Tirsa(eliana.tirsacs.pub.ro)
Cristina Teodora Andreica(cristinandreicayahoo.com)
Romulus Andreica(academiacomercialayahoo.com)
Mihai Aristotel Ungureanu(mugurelionutgmail.com)

Abstract: In this paper we present some new, practical, geometric optimization techniques for computing polygon partitions, 1D and 2D point, interval, square and rectangle covers, as well as 1D and 2D interval and rectangle K-centers. All the techniques we present have immediate applications to several cost optimization and facility location problems which are quite common in practice. The main technique employed is dynamic programming, but we also make use of efficient data structures and fast greedy algorithms.

Keywords: polygon partition, point cover, interval cover, rectangle cover, interval K-center, dynamic programming

Category 1: Applications -- Science and Engineering (Facility Planning and Design )

Category 2: Other Topics (Dynamic Programming )

Category 3: Combinatorial Optimization (Other )

Citation: Extended version of the paper with the same title, published in Proceedings of the 9th WSEAS International Conference on Mathematics and Computers in Business and Economics, pp. 173-178, Bucharest, Romania, 24-26 June 2008.

Download: [PDF]

Entry Submitted: 10/20/2008
Entry Accepted: 10/20/2008
Entry Last Modified: 10/20/2008

Modify/Update this entry