article

Free access

An Optimal Algorithm for Finding the Kernel of a Polygon

Authors:

D. T. Lee,

F. P. PreparataAuthors Info & Claims

Journal of the ACM (JACM), Volume 26, Issue 3

Pages 415 - 421

https://doi.org/10.1145/322139.322142

Published: 01 July 1979 Publication History

PDF eReader

Reference

[1]

SHAMOS, M I, AND HOEY, D Geometric intersection problems 17th Annual Syrup on Foundattons of Computer Science, Houston, Tex, Oct 1976, pp 208-215 (IEEE)

Google Scholar

Cited By

View all

Asiler MSahillioğlu Y(2024)KerGen: A Kernel Computation Algorithm for 3D Polygon MeshesComputer Graphics Forum10.1111/cgf.1513743:5Online publication date: 31-Jul-2024
https://doi.org/10.1111/cgf.15137
Asiler MSahillioğlu Y(2024)3D geometric kernel computation in polygon mesh structuresComputers & Graphics10.1016/j.cag.2024.103951122(103951)Online publication date: Aug-2024
https://doi.org/10.1016/j.cag.2024.103951
Nilsson BPacker E(2024)Approximation Algorithms for the Two-Watchman Route in a Simple PolygonAlgorithmica10.1007/s00453-024-01245-086:9(2845-2884)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s00453-024-01245-0
Show More Cited By

Index Terms

An Optimal Algorithm for Finding the Kernel of a Polygon
1. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

On finding an empty staircase polygon of largest area (width) in a planar point-set

This paper presents an algorithm for identifying a maximal empty-staircase-polygon (MESP) of largest area, among a set of n points on a rectangular floor. A staircase polygon is an isothetic polygon bounded by two monotonically rising (falling) ...
An Optimal Algorithm for Determining the Visibility of a Polygon from an Edge

In many computer applications areas such as graphics, automated cartography, image processing, and robotics the notion of visibility among objects modeled as polygons is a recurring theme. This paper is concerned with the visibility of a simple polygon ...
An Optimal Algorithm for Detecting Weak Visibility of a Polygon

Notation and a theorem are presented which, using a result of B. Chazelle and L.J. Guibas (1985), enable the authors to design an O(n log n) algorithm for reporting all visibility edges of a given n-vertex polygon. Improving on this bound to O(n) is ...

Comments

Information & Contributors

Information

Published In

Journal of the ACM Volume 26, Issue 3

july 1979

217 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/322139

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1979

Published in JACM Volume 26, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

140
Total Citations
View Citations
2,120
Total Downloads

Downloads (Last 12 months)234
Downloads (Last 6 weeks)31

Reflects downloads up to 22 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Asiler MSahillioğlu Y(2024)KerGen: A Kernel Computation Algorithm for 3D Polygon MeshesComputer Graphics Forum10.1111/cgf.1513743:5Online publication date: 31-Jul-2024
https://doi.org/10.1111/cgf.15137
Asiler MSahillioğlu Y(2024)3D geometric kernel computation in polygon mesh structuresComputers & Graphics10.1016/j.cag.2024.103951122(103951)Online publication date: Aug-2024
https://doi.org/10.1016/j.cag.2024.103951
Nilsson BPacker E(2024)Approximation Algorithms for the Two-Watchman Route in a Simple PolygonAlgorithmica10.1007/s00453-024-01245-086:9(2845-2884)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s00453-024-01245-0
Dahlin AKarayiannidis Y(2023)Creating Star Worlds: Reshaping the Robot Workspace for Online Motion PlanningIEEE Transactions on Robotics10.1109/TRO.2023.327902939:5(3655-3670)Online publication date: 1-Oct-2023
https://dl.acm.org/doi/10.1109/TRO.2023.3279029
Fadila HYoun Hong QElber G(2023)Kernel-based Construction Operators for Boolean Sum and Ruled GeometryComputer Aided Geometric Design10.1016/j.cagd.2023.102205(102205)Online publication date: May-2023
https://doi.org/10.1016/j.cagd.2023.102205
Lee SChwa K(2023)Some chain visibility problems in a simple polygonAlgorithmica10.1007/BF018404005:1-4(485-507)Online publication date: 22-Mar-2023
https://dl.acm.org/doi/10.1007/BF01840400
Dobkin DSouvaine D(2023)Computational geometry in a curved worldAlgorithmica10.1007/BF018403975:1-4(421-457)Online publication date: 22-Mar-2023
https://dl.acm.org/doi/10.1007/BF01840397
McCoy BZhu BDutt A(2023)Guarding Precise and Imprecise Polyhedral Terrains with SegmentsCombinatorial Optimization and Applications10.1007/978-3-031-49614-1_24(323-336)Online publication date: 9-Dec-2023
https://doi.org/10.1007/978-3-031-49614-1_24
Director HRaftery A(2022)Contour Models for Physical Boundaries Enclosing Star-Shaped and Approximately Star-Shaped PolygonsJournal of the Royal Statistical Society Series C: Applied Statistics10.1111/rssc.1259271:5(1688-1720)Online publication date: 19-Sep-2022
https://doi.org/10.1111/rssc.12592
Huber LSlotine JBillard A(2022)Avoiding Dense and Dynamic Obstacles in Enclosed Spaces: Application to Moving in CrowdsIEEE Transactions on Robotics10.1109/TRO.2022.316478938:5(3113-3132)Online publication date: Oct-2022
https://doi.org/10.1109/TRO.2022.3164789
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Reference

Cited By

Index Terms

Recommendations

On finding an empty staircase polygon of largest area (width) in a planar point-set

An Optimal Algorithm for Determining the Visibility of a Polygon from an Edge

An Optimal Algorithm for Detecting Weak Visibility of a Polygon

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations