File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: A unifying approach for a class of problems in the computational geometry of polygons

TitleA unifying approach for a class of problems in the computational geometry of polygons
Authors
KeywordsComputational Geometry
Locality
Monotonicity
Polygon Distances
Polygon Intersection
Unimodality
Issue Date1985
PublisherSpringer Verlag. The Journal's web site is located at http://link.springer.de/link/service/journals/00371/index.htm
Citation
The Visual Computer, 1985, v. 1 n. 2, p. 124-132 How to Cite?
AbstractA generalized problem is defined in terms of functions on sets and illustrated in terms of the computational geometry of simple planar polygons. Although its apparent time complexity is O(n2), the problem is shown to be solvable for several cases of interest (maximum and minimum distance, intersection detection and rerporting) in O(n log n), O(n) or O(log n) time, depending on the nature of a specialized "selection" function. (Some of the cases can also be solved by the Voronoi diagram method; but time complexity increases with that approach.) A new use of monotonicity and a new concept of "locality" in set mappings contribute significantly to the derivation of the results. © 1985 Springer-Verlag.
Persistent Identifierhttp://hdl.handle.net/10722/152218
ISSN
2023 Impact Factor: 3.0
2023 SCImago Journal Rankings: 0.778
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorChin, Fen_US
dc.contributor.authorSampson, Jen_US
dc.contributor.authorWang, CAen_US
dc.date.accessioned2012-06-26T06:36:35Z-
dc.date.available2012-06-26T06:36:35Z-
dc.date.issued1985en_US
dc.identifier.citationThe Visual Computer, 1985, v. 1 n. 2, p. 124-132en_US
dc.identifier.issn0178-2789en_US
dc.identifier.urihttp://hdl.handle.net/10722/152218-
dc.description.abstractA generalized problem is defined in terms of functions on sets and illustrated in terms of the computational geometry of simple planar polygons. Although its apparent time complexity is O(n2), the problem is shown to be solvable for several cases of interest (maximum and minimum distance, intersection detection and rerporting) in O(n log n), O(n) or O(log n) time, depending on the nature of a specialized "selection" function. (Some of the cases can also be solved by the Voronoi diagram method; but time complexity increases with that approach.) A new use of monotonicity and a new concept of "locality" in set mappings contribute significantly to the derivation of the results. © 1985 Springer-Verlag.en_US
dc.languageengen_US
dc.publisherSpringer Verlag. The Journal's web site is located at http://link.springer.de/link/service/journals/00371/index.htmen_US
dc.relation.ispartofThe Visual Computeren_US
dc.subjectComputational Geometryen_US
dc.subjectLocalityen_US
dc.subjectMonotonicityen_US
dc.subjectPolygon Distancesen_US
dc.subjectPolygon Intersectionen_US
dc.subjectUnimodalityen_US
dc.titleA unifying approach for a class of problems in the computational geometry of polygonsen_US
dc.typeArticleen_US
dc.identifier.emailChin, F:chin@cs.hku.hken_US
dc.identifier.authorityChin, F=rp00105en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1007/BF01898356en_US
dc.identifier.scopuseid_2-s2.0-0022142486en_US
dc.identifier.volume1en_US
dc.identifier.issue2en_US
dc.identifier.spage124en_US
dc.identifier.epage132en_US
dc.identifier.isiWOS:000209831300009-
dc.publisher.placeGermanyen_US
dc.identifier.scopusauthoridChin, F=7005101915en_US
dc.identifier.scopusauthoridSampson, J=7102092449en_US
dc.identifier.scopusauthoridWang, CA=7501646353en_US
dc.identifier.issnl0178-2789-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats