Greedy Triangulation Algorithm

Thread View: ne.seminars

1 messages

[T] Back to Threads [V] Tree View [G] Group Articles

1 total messages Started by David Kotz Fri, 16 Oct 1992 22:25

#60

Author: David Kotz
Date: Fri, 16 Oct 1992 22:25

35 lines
1943 bytes

                          Dartmouth College
                      Computer Science Colloqium

                             Matt Dickerson
                           Middlebury College

          A Fast Expected-Case Greedy Triangulation Algorithm
                based on the Rank of the Longest Edge

                     Wednesday, October 21, 1992
                               4:00 PM
                           102 Bradley Hall

         Refreshments at 3:30pm in Faculty Lounge, 2nd floor

Abstract

For a uniform distribution of n points in a disc, we show that the
expected value of the rank of the longest edge in the greedy
triangulation is on the order of n 4/3.  Based on this result, on the
triangulation compatibility test method of Gilbert, and on the
enumeration algorithm of Dickerson and Drysdale, we then give a new
greedy triangulation algorithm which for uniform distributions in a
disc requires O n 4/3n time and O n 4/3 space in the expected case.

For additional info please contact David Kotz at David.Kotz@dartmouth.edu.

Directions to Bradley Hall:
	   anonymous ftp to sunapee.dartmouth.edu in pub/directions
-- 
-----------------
Mathematics and Computer Science
Dartmouth College, 6188 Bradley Hall, Hanover NH 03755-3551
email: David.Kotz@Dartmouth.edu    or   dfk@cs.dartmouth.edu

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads