Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!cs.utexas.edu!helios!gordon
From: gordon@cs.tamu.edu (Dan Gordon)
Newsgroups: comp.graphics
Subject: Re: smallest polygon enclosing a point
Message-ID: <6492@helios.TAMU.EDU>
Date: 11 Jul 90 01:31:48 GMT
References: <1990Jul11.010350.10088@agate.berkeley.edu<
Sender: usenet@helios.TAMU.EDU
Organization: Computer Science Department, Texas A&M University
Lines: 16

In article <1990Jul11.010350.10088@agate.berkeley.edu< larry@pylos.cchem.berkeley.edu (Raymond L. June) writes:
<
<	I have a problem I'd like to see if has been solved before and
<therefore appeal to this group for a little help. I have a point (call
<it the origin) and a number of lines (not colinear) in the same plane.
<What I'd like to compute is the smallest polygon formed from the
<intersection of the aforementioned lines which encloses the origin.
<The 'physics' of the problem says pretty strongly that the lines
<will always 'surround' the origin so that I will be rendering a
<closed polygon. 

For every line, consider the half-plane defined by the line and the
side on which the origin lies. What you are looking for is the
intersection of all these half-planes. This can be done in optimal
time theta(N log N) - see "Computational Geometry" by Preparata & 
Shamos, Section 7.2.4, pp. 279-282.