﻿ Convex Hull ~ Applications

# Applications

## Theory comes from practices, and applies to them.

Convex hull algorithm is a fundamental algorithm in computation geometry, on which are many algorithms in computation geometry based. Also there are a lot of applications that use convex hull algorithm. In this section, we will introduce serveral real applications of the convex hull algorithm to you.

### Computer Visualization, Ray Tracing, Video Games, Replacement of Bounding Boxes

Bounding boxes are used to an approximate location of an object in question and as a very simple descriptor of its shape. For example, in computational geometry and its applications when it is required to find intersections in the set of objects, the initial check is the intersections between their bounding boxes. Since it is usually a much less expensive operation than the check of the actual intersection (because it only requires comparisons of coordinates), it allows to quickly exclude from checks the pairs that are far apart. Convex hull can be a candidate for replacement of bounding boxes in these situations.

### Path Finding - Embedded AI of Mars mission Rovers

Mars Exploration Rover Mission has amassed an enormous amount of scientific information related to the Martian geology and atmosphere, as well as providing some astronomical observations from Mars. This article covers information gathered by the Opportunity rover during the initial phase of its mission. Information on science gathered by Spirit can be found mostly in the Spirit rover article.

The ongoing unmanned Mars exploration mission, commenced in 2003 sent two robotic rovers, Spirit and Opportunity, to explore the Martian surface and geology. The mission was led by Project Manager Peter Theisinger of NASA's Jet Propulsion Laboratory and Principal Investigator Steven Squyres, professor of astronomy at Cornell University.

Primary among the mission's scientific goals is to search for and characterize a wide range of rocks and soils that hold clues to past water activity on Mars. In recognition of the vast amount of scientific information amassed by both rovers, two asteroids have been named in their honor: 37452 Spirit and 39382 Opportunity.

### Geographical Information Systems (GIS) - Computing Accessibility Maps

A geographic information system (GIS), also known as a geographical information system or geospatial information system, is a system for capturing, storing, analyzing and managing data and associated attributes which are spatially referenced to the Earth.

In the strictest sense, it is an information system capable of integrating, storing, editing, analyzing, sharing, and displaying geographically-referenced information. In a more generic sense, GIS is a tool that allows users to create interactive queries (user created searches), analyze the spatial information, edit data, maps, and present the results of all these operations. Geographic information science is the science underlying the geographic concepts, applications and systems, taught in degree and GIS Certificate programs at many universities.

Geographic information system technology can be used for scientific investigations, resource management, asset management, Environmental Impact Assessment, Urban planning, cartography, criminology, history, sales, marketing, and logistics. For example, GIS might allow emergency planners to easily calculate emergency response times in the event of a natural disaster, GIS might be used to find wetlands that need protection from pollution, or GIS can be used by a company to site a new business to take advantage of a previously underserved market.

### Visual Pattern Matching - Detecting Car License Plates

Pattern recognition aims to classify data (patterns) based on either a priori knowledge or on statistical information extracted from the patterns. The patterns to be classified are usually groups of measurements or observations, defining points in an appropriate multidimensional space. This is in contrast to pattern matching, where the pattern is rigidly specified.

Within medical science pattern recognition creates the basis for CAD Systems (Computer Aided Diagnosis). CAD describes a procedure that supports the doctor's interpretations and findings.

A complete pattern recognition system consists of a sensor that gathers the observations to be classified or described; a feature extraction mechanism that computes numeric or symbolic information from the observations; and a classification or description scheme that does the actual job of classifying or describing observations, relying on the extracted features.

### Verification Methods - Bounding of Number Decision Diagrams

Number Decision Diagrams (NDDs) are finite state automata representing sets of integer vectors. They have recently been proposed as an efficient data structure for representing sets definable in Presburger arithmetic.

### Geometry - Diameter Computation

For example, consider the problem of finding the diameter of a set of points, which is the pair of points a maximum distance apart. The diameter will always be the distance between two points on the convex hull. The O(nlogn) algorithm for computing diameter proceeds by first constructing the convex hull, then for each hull vertex finding which other hull vertex is farthest away from it. This so-called "rotating-calipers" method can be used to move efficiently from one hull vertex to another.

### Books on Convex Hull

Computational Geometry: Algorithms and Applications
Mark de Berg, M.van Krefeld, etc, Second Edition
Computational Geometry and Computer Graphics in C++
Michael J.Laszlo
Computational Geometry in C
Joseph O’Rourke, Second Edition

### Cooperations

Home
Chen Cheng
History
Ruan Binbin
Applications
Yu Jie
Contact & Web Design
Jia Qi