UWA Logo
  Faculty Home | School Home | Internal Page | Awesome Animations   
           
Home
About the School
Contact and People
Future Undergraduate Students
Prospective Postgraduates
Current Students
Current Postgraduates
Research
Research Areas Research Areas Research Areas
Research Seminars Research Seminars Research Seminars
20082008 2008 2008
20072007 2007 2007
20062006 2006 2006
20052005 2005 2005
20042004 2004 2004
20032003 2003 2003
20022002 2002 2002
20012001 2001 2001
20002000 2000 2000
19991999 1999 1999
19981998 1998 1998
School Research Conferences School Research Conferences School Conferences
Tech Reports Tech Reports Tech Reports
Distinguished Visitors Distinguished Visitors Distinguished Visitors
Research Opportunities for Students Research Opportunities for Students Research Opportunities ...
Research Project Suggestions Research Project Suggestions Research Project Sugges...
IT News
Awards
Industry Links and Prizes
School and IT Information
Other
Internal Information

Research Seminars - October 30, 1998

Seminar Announcement


Title: Efficient Enumeration of Extreme Points in Higher Dimensions
Speaker: Laxmi
  Computer Science
Date: Friday 30th October, 1998
Time: 3pm
Venue: Seminar Room 1.24

Abstract

The extreme points of a point set are the vertices of its convex hull. In this talk, we present an efficient and output-sensitive algorithm for enumerating extreme points of a point set in any dimension d. Our algorithm runs in O(nm) time and O(n) space when the dimension d is fixed. Here, n is the total number of points in the set and m is the total number of extreme points reported. This improves the previously best known complexity for this problem when m<=4.

Top of Page