Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
The approximation algorithms for a class of multiple-choice problem
Wang Y., Xu Y. Theoretical Computer Science654 164-174,2016.Type:Article
Date Reviewed: Aug 8 2017

This paper is concerned with the problem of computing coverings of a set of colored points in a plane (I personally find the title slightly misleading). In particular, the initial data consists of a set of points in the plane that are colored with colors from a given set of colors. The problems investigated are then certain “optimal hull problems,” like finding the smallest circle enclosing a set of points containing a least one point of each color.

The main results of the paper are new algorithms that do not need prior computations of Voronoi diagrams and/or give better approximations than currently known results.

The paper starts with an overview of existing literature on the problem and a layout of the main results and how they are going to be presented. This is followed by some basic definitions needed for understanding the rest of the discussion.

The main body of the paper consists of three sections presenting the algorithms and the mathematical proof of their properties.

The paper is understandable, although some language glitches might cause some confusion. The diagrams greatly help in understanding the ideas. Some information on the practical relevance of the work would have been nice. I could not get a feeling on whether the improvement in approximation really makes a difference or whether the presented algorithms are as equally easy to implement as the existing ones.

Reviewer:  Markus Wolf Review #: CR145462 (1710-0687)
Bookmark and Share
 
Computational Geometry And Object Modeling (I.3.5 )
 
 
Approximation (G.1.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Computational Geometry And Object Modeling": Date
Computer image synthesis: shapes
Crow F.  Computer culture: the scientific, intellectual, and social impact of the computer (, New York,611984. Type: Proceedings
Jul 1 1986
Table-driven algorithms for generating space-filling curves
Griffiths J. Computer-Aided Design 17(1): 37-41, 1985. Type: Article
Feb 1 1988
Automatic curve fitting with quadratic B-spline functions and its applications to computer-assisted animation
Yang M., Kim C., Cheng K., Yang C., Liu S. Computer Vision, Graphics, and Image Processing 33(3): 346-362, 1986. Type: Article
Sep 1 1986
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy