×

### Let's log you in.

or

Don't have a StudySoup account? Create one here!

×

or

## COMPUTATIONL GEOMETRY

by: Carlo Monahan

16

0

4

# COMPUTATIONL GEOMETRY COT 5520

Marketplace > University of Florida > OTHER > COT 5520 > COMPUTATIONL GEOMETRY
Carlo Monahan
UF
GPA 3.85

Staff

These notes were just uploaded, and will be ready to view shortly.

Either way, we'll remind you when they're ready :)

Get a free preview of these Notes, just enter your email below.

×
Unlock Preview

COURSE
PROF.
Staff
TYPE
Class Notes
PAGES
4
WORDS
KARMA
25 ?

## Popular in OTHER

This 4 page Class Notes was uploaded by Carlo Monahan on Friday September 18, 2015. The Class Notes belongs to COT 5520 at University of Florida taught by Staff in Fall. Since its upload, it has received 16 views. For similar materials see /class/206634/cot-5520-university-of-florida in OTHER at University of Florida.

×

## Reviews for COMPUTATIONL GEOMETRY

×

×

### What is Karma?

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/18/15
CS 373 NonLecture E Convex Hulls Fall 2002 E Convex Hulls E1 De nitions We are given a set P of n points in the plane We want to compute something called the convex hull of P lntuitively the convex hull is what you get by driving a nail into the plane at each point and then wrapping a piece of string around the nails More formally the convex hull is the smallest convex polygon containing the points 0 polygon A region of the plane bounded by a cycle of line segments called edges joined end to end in a cycle Points where two successive edges meet are called vertices o convex For any two points p q inside the polygon the line segment 17 is completely inside the polygon o smallest Any convex proper subset of the convex hull excludes at least one point in P This implies that every vertex of the convex hull is a point in P We can also de ne the convex hull as the largest convex polygon whose vertices are all points in P or the unique convex polygon that contains P and whose vertices are all points in P Notice that P might have interior points that are not vertices of the convex hull A set of points and its convex hull Convex hull vertices are black interior points are white Just to make things concrete we will represent the points in P by their Cartesian coordinates in two arrays X1n and Y1 We will represent the convex hull as a circular linked list of vertices in counterclockwise order if the ith point is a vertex of the convex hull nexti is index of the next vertex counterclockwise and predi is the index of the next vertex clockwise otherwise nexti pred 0 It doesn t matter which vertex we choose as the head of the list The decision to list vertices counterclockwise instead of clockwise is arbitrary To simplify the presentation of the convex hull algorithms 1 will assume that the points are in general position meaning in this context that no three points lie on a common line This is just like assuming that no two elements are equal when we talk about sorting algorithms If we wanted to really implement these algorithms we would have to handle colinear triples correctly or at least consistently This is fairly easy but de nitely not trivial E2 Simple Cases Computing the convex hull of a single point is trivial we just return that point Computing the convex hull of two points is also trivial For three points we have two different possibilities 7 either the points are listed in the array in clockwise order or counterclockwise order Suppose our three points are a l7 c7 d and 67 f given in that order and for the moment let s also suppose that the rst point is furthest to the CS 373 NonLecture E Convex Hulls Fall 2002 left so a lt c and a lt f Then the three points are in counterclockwise order if and only if the line a bc d is less than the slope of the line a Z7e7 f d 7 I f 7 b 7lt c7a 67a counterclockwise ltgt Since both denominators are positive we can rewrite this inequality as follows counterclockwise ltgt f 7 bc 7 a gt d 7 be 7 a This nal inequality is correct even if 2717 is not the leftmost point If the inequality is reversed then the points are in clockwise order If the three points are colinear remember we re assuming that never happens then the two expressions are equal e 0 ad Three points in counterclockwise order 417 Another way of thinking about this counterclockwise test is that we re computing the cross pmduct of the two vectors c7 d 7 2717 and e f 7 a b which is de ned as a 2 x 2 determinant counterclockwise ltgt C T a d T 6 gt 0 e 7 a f 7 b We can also write it as a 3 x 3 determinant l a b counterclockwise ltgt 1 c d gt 0 l e f All three boxed expressions are algebraically identical This counterclockwise test plays exactly the same role in convex hull algorithms as comparisons play in sorting algorithms Computing the convex hull of of three points is analogous to sorting two numbers either they re in the correct order or in the opposite order E3 Jarvis s Algorithm Wrapping Perhaps the simplest algorithm for computing convex hulls simply simulates the process of wrapping a piece of string around the points This algorithm is usually called Jarvis s march but it is also referred to as the ngt wmppmg algorithm Jarvis s march starts by computing the leftmost point 6 225 the point whose ac coordinate is smallest since we know that the left most point must be a convex hull vertex Finding 6 clearly takes linear time CS 373 NonLecture E Convex Hulls Fall 2002 The execution of Jarvis s March Then the algorithm does a series of pivoting steps to nd each successive convex hull vertex starting with Z and continuing until we reach 6 again The vertex immediately following a point p is the point that appears to be furthest to the right to someone standing at p and looking at the other points In other words if q is the vertex following p and r is any other input point then the triple p 1quot is in counter clockwise order We can nd each successive vertex in linear time by performing a series of 0n counter clockwise tests JARVISMARCHX1 n Y1 n 5 H1 for i H 2 to n if lt XV 5 Hi I 6 repeat q H p 1 Make sure I7 739 qgtgt for i H 2 to n if CCWpiq q z newtlpl H q prevlql H17 17 Eq until p Z Since the algorithm spends 0n time for each convex hull vertex the worst case running time is 0n2 However this nai39ve analysis hides the fact that if the convex hull has very few vertices Jarvis s march is extremely fast A better way to write the running time is 0nh where h is the number of convex hull vertices In the worst case h n and we get our old 0n2 time bound but in the best case h 3 and the algorithm only needs 0n time Computational geometers call this an outputsensitive algorithm the smaller the output the faster the algorithm E4 Divide and Conquer Splitting The behavior of Jarvis s marsh is very much like selection sort repeatedly nd the item that goes in the next slot In fact most convex hull algorithms resemble some sorting algorithm For example the following convex hull algorithm resembles quicksort We start by choosing a pivot point p Partitions the input points into two sets L and R containing the points to the left 3

×

×

### BOOM! Enjoy Your Free Notes!

×

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

Bentley McCaw University of Florida

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Allison Fischer University of Alabama

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over \$600 per month. I LOVE StudySoup!"

Jim McGreen Ohio University

Forbes

#### "Their 'Elite Notetakers' are making over \$1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!
×

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com